Problem Description

There are $ N $ slimes lined up on a number line. The $ i $th slime from the left is at position $ x_i $.

It is guaranteed that $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^9$.

Niwango performs $ N-1 $ operations. The $ i $th operation consists of the following steps:

• Choose an integer between $ 1 $ and $ N-i $ with equal probability (let's call it $ k $)
• Move the $ k $th slime from the left to the position of the slime next to it
• Then, fuse the two slimes at the same position into one slime

Find the expected value of the total distance moved by the slimes multiplied by $ (N-1)! $ (which can be shown to be an integer) modulo $ 10^9+7 $. Note that if a fused slime moves, it counts as the movement of one slime.

Input Format

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

$ N $ $ x_1 $ $ x_2 $ $\ldots$ $ x_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

5

Sample Input #2

12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932

Sample Output #2

750927044

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^9$
• $ x_i $ are integers

Partial Points

• Correctly solving all test cases where $N \leq 2000$ will award $ 400 $ points.

Sample Explanation 1

• With probability $\frac{1}{2}$, the first slime from the left is chosen first, and the total distance moved in this case is $ 2 $.
• With probability $\frac{1}{2}$, the second slime from the left is chosen first, and the total distance moved in this case is $ 3 $.
• The expected total distance moved is $ 2.5 $, and multiplying this by $ 2! $ gives $ 5 $, which is the answer.

Sample Explanation 2

• Find the expected value multiplied by $ (N-1)! $ modulo $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分