Problem Statement

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

It is guaruanteed that 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.

Niwango will perform N-1 operations. The i-th operation consists of the following procedures:

• Choose an integer k between 1 and N-i (inclusive) with equal probability.
• Move the k-th slime from the left, to the position of the neighboring slime to the right.
• Fuse the two slimes at the same position into one slime.

Find the total distance traveled by the slimes multiplied by (N-1)! (we can show that this value is an integer), modulo (10^{9}+7). If a slime is born by a fuse and that slime moves, we count it as just one slime.

Constraints

• 2 \leq N \leq 10^{5}
• 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}
• x_i is an integer.

Subtasks

• 400 points will be awarded for passing the test cases satisfying N \leq 2000.

Sample Input 1

3
1 2 3

Sample Output 1

5

• With probability \frac{1}{2}, the leftmost slime is chosen in the first operation, in which case the total distance traveled is 2.
• With probability \frac{1}{2}, the middle slime is chosen in the first operation, in which case the total distance traveled is 3.
• The answer is the expected total distance traveled, 2.5, multiplied by 2!, which is 5.

Sample Input 2

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

Sample Output 2

750927044

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