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>
using namespace std;

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

/*
*/

using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int,int>;

const int mod = 1e9+7;

int mpow(int a, int b)
{
  if(b == 0) return 1; 
  return mpow(a*a%mod, b/2)*(b%2?a:1)%mod;
}

signed main() {
  int n;
  cin >> n;

  vi x(n);
  rep(i, 0, n) cin >> x[i];

  vi d(n-1);
  rep(i, 0, n-1) d[i] = x[i+1] - x[i];

  vi fac(n), inv(n);
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  rep(i, 2, n) fac[i] = fac[i-1]*i%mod, inv[i] = mpow(i, mod-2)%mod;

  int ans = 0, s = 0;
  rep(i, 0, n-1){
    (s += inv[i+1]) %= mod;
    (ans += d[i]*s%mod) %= mod;
  }
  cout << ans*fac[n-1]%mod << endl;

  return 0;
}
