Summing Absolute Differences

You are given an array of n positive integers where 1 ≤ n ≤ 1000 and each element is at most 10⁶. Your task is to compute the sum of the absolute differences between every pair of distinct elements in the array. Since the answer can be very large, output the result modulo \(10^9+7\).

More formally, if the array is \(a = [a_1, a_2, \dots, a_n]\), you need to find:

[ \text{Answer} = 2\sum_{1 \leq i < j \leq n} |a_j - a_i| \mod (10^9+7) ]

Note: The factor of 2 arises because each pair is counted twice when considering all ordered pairs of distinct elements.

inputFormat

The input is given from the standard input in the following format:

1. The first line contains a single integer n representing the number of elements in the array.
2. The second line contains n space-separated integers, where each integer is an element of the array.

Constraints: 1 ≤ n ≤ 1000 and 1 ≤ a[i] ≤ 10⁶ for all valid i.

outputFormat

Output a single integer which is the sum of the absolute differences between all pairs of distinct elements, modulo \(10^9+7\). The result should be printed to the standard output.

## sample

3
1 2 3

8

</p>