EarthX is a space company owned by billionaire TomLon Tusk that is seeking to IPO at an astonishing valuation of ~1.75 trillion. They are seeking inclusion in the Nasdaq 100 as part of their listing, allowing pension funds and such to provide sweet exit liquidity to Tusk and his friends.

As part of the preparation for IPO, TomLon is driving heavy cost-cutting, involving laying off 1,000,000 workers, tightening up supply chains, etc. One of EarthX's primary products is GroundLink, a satellite WiFi service. They maintain some ground towers, but these towers interfere with each other, so they want you to calculate the total instability of the system using some certain formulas.

There are ~n~ ground towers at integer coordinates ~x_1,\dots,x_n~. Each tower emits a signal, and the interference between two towers at positions ~x_i~, ~x_j~ is given as

$$\displaystyle f(x_i,x_j) = |x_i-x_j|\times\left(|x_i-x_j|+1\right) $$

The total system instability is defined as:

$$\displaystyle \sum_{1\leq i < j \leq n}f(x_i,x_j) $$

i.e., the interference between every (unordered) pair of towers.

Can you calculate this metric for them, so they can use it to cut costs and provide TomLon his sweet golden parachute? The researchers also asked you to output the stability modulo ~10^9+7~, as they are running on ancient 32-bit systems and don't want your value to blow up their servers.

Input

The first line contains an integer ~n~ ~(1 \leq n \leq 2\times 10^5)~, the number of signal towers.

The second line contains ~n~ space-separated integers ~x_1, x_2, \dots, x_n~ ~(|x_i| \leq 10^9)~.

Output

Output the total system instability, modulo ~10^9+7~.

Example

Input 1

3
1 2 3

Output 1

10

We can just enumerate all pairs

• ~(1,2)~: ~|1-2| \times (|1-2|+1)=1\times2=2~
• ~(1,3)~: ~|1-3| \times (|1-3|+1)=2\times3=6~
• ~(2,3)~: ~|2-3| \times (|2-3|+1)=1\times2=2~

So the result is ~2+6+2=10~.

Input 2

4
-2 -1 0 2

Output 2

48

• ~(-2,-1)~: ~1\times2=2~
• ~(-2,0)~: ~2\times3=6~
• ~(-2,2)~: ~4\times5=20~
• ~(-1,0)~: ~1\times2=2~
• ~(-1,2)~: ~3\times4=12~
• ~(0,2)~: ~2\times3=6~

The result is thus ~2+6+20+2+12+6=48~

Input 3

4
0 5 0 0

Output 3

90