A. Krosh and new sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh has an array of $$$n$$$ integers. Help him to calculate the following value: $$$\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n |a_i - a_j| * (a_i + a_j)$$$. Output it modulo $$$10^9+7$$$.

Input

In the first line you are given number $$$2 \le n \le 2 * 10^5$$$. In the second line you are given array of $$$n$$$ non-negative integers $$$1 \le a_i \le 10^8$$$.

Output

Output answer modulo $$$10^9+7$$$.

Examples
Input
5
2 3 4 5 1
Output
120
Input
2
100000000 100000000
Output
0
Input
10
1 100000000 1 100000000 100000000 1 1 100000000 100000000 1
Output
249999989