Tree Planting

Time limit2sMemory limit128 MB

Summary

Plant trees in order and compute the product, modulo 1e9+7, of the sum of distances from each new tree to all previously planted trees.

Level: Medium6 of 10
Topics: Segment tree, Prefix sum, Math
Solved: No attempts yet

Problem

There are N trees numbered from 1 to N. Tree i will be planted at coordinate X[i].

Dongho plants the trees in order from tree 1 to tree N. Planting tree 1 costs 0. For every later tree, the cost is the sum of its distances to all trees that have already been planted. Therefore, the cost of planting tree 3 is the distance to tree 1 plus the distance to tree 2.

Find the product of the planting costs for trees 2 through N.

Input

The first line contains the number of trees N (2 <= N <= 200,000).

Each of the next N lines contains one coordinate, given in order from tree 1 to tree N. Each coordinate is an integer greater than or equal to 0 and less than 200,000.

Output

Print the product of all costs modulo 1,000,000,007.

Examples5

Example 1
Input
```
5
3
4
5
6
7
```
Expected output
```
180
```
Example 2
Input
```
3
5
13
9
```
Expected output
```
64
```
Example 3
Input
```
4
1
8
15
1
```
Expected output
```
3087
```

Example 4

Input

Expected output

591860767

Example 5

Input

Expected output

499739175