Tree Planting

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.

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.

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