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
#include <bits/stdc++.h>

#define MOD 1000000007ll
#define INV2 500000004ll

using namespace std;

typedef long long ll;
ll a[100005];
ll fact[100005];
ll dp[100005];

ll fast_pow(ll n, ll e){
    if(!e)
        return 1ll;
    ll tmp = (fast_pow(n,e/2ll));
    tmp = (tmp*tmp)%MOD;
    if(e&1)
        return (tmp*n)%MOD;
    return tmp;
}

int main(){
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    fact[0] = 1;
    for(int i = 1; i<=n; i++)
        fact[i] = (fact[i-1]*i)%MOD;
    for(int i = 0; i<n; i++)
        cin >> a[i];
    dp[1] = fact[n-1];
    for(int i = 2; i<n; i++){
        dp[i] = dp[i-1];
        ll adder = (fact[n-1]*fast_pow(i,MOD-2ll));
        dp[i] = (dp[i]+adder)%MOD;
    }
    ll ans = 0;
    for(int i = 1; i<n; i++){
        ll adder = (a[i]-a[i-1])*dp[i];
        adder %= MOD;
        ans = (ans+adder)%MOD;
    }
    cout << ans << "\n";
    return 0;
}