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.

Input

Input is given from Standard Input in the following format:


N
x_1 x_2 \ldots x_N


Output

Print the answer.

Examples

Input

3
1 2 3


Output

5


Input

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


Output

750927044

n = int(input())

A = list(map(int,input().split()))

C = []
for i in range(n-1):
    C.append(A[i+1]-A[i])
n -= 1
A=C[:]

mod  =10**9+7

B = [0] * (n+1)


l=n+5
M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def inv(x, y):  # xのmod yでの逆元を返す関数
    yy = y - 2
    ans = 1
    while yy > 0:
        if yy % 2 == 1:
            ans = (ans * x) % y
        x = (x**2) % y
        yy //= 2
    return ans

for i in range(1, n+1):
    B[i] = (inv(i,mod) * M[n-1]) % mod


p=M[n]
ans = p*A[0]
for i in range(1, n):
    
    p = (p + M[n-1] + B[i+1]*(n-1-i)) % mod
    # print("p",p)
    ans = (ans+p*A[i]) % mod
print(ans%mod)