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
# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2,x+1):
        res=res*i%mod
    return res

# combination nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        return fact(n)*inv(fact(r))*inv(fact(n-r))%mod

mod=10**9+7

N=int(input())
x=[0]
x.extend(list(map(int,input().split())))
invs=[inv(d) for d in range(N)]
# print(invs)
ans=0;s=0
for d in range(1,(N-1)//2+1):
    s=(s+x[N-d]-x[d])%mod
    ans=(ans+s*invs[d]*invs[d+1])%mod
    if d!=N-d-1:
        ans=(ans+s*invs[N-d-1]*invs[N-d])%mod
for i in range(1,N):
    ans=(ans+(x[N]-x[i])*invs[N-i])%mod
ans=ans*fact(N-1)%mod

print(ans)