You are given an array a of length n. We define fa the following way:

  * Initially fa = 0, M = 1; 
  * for every 2 ≤ i ≤ n if aM < ai then we set fa = fa + aM and then set M = i. 



Calculate the sum of fa over all n! permutations of the array a modulo 109 + 7.

Note: two elements are considered different if their indices differ, so for every array a there are exactly n! permutations.

Input

The first line contains integer n (1 ≤ n ≤ 1 000 000) — the size of array a.

Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print the only integer, the sum of fa over all n! permutations of the array a modulo 109 + 7.

Examples

Input

2
1 3


Output

1

Input

3
1 1 2


Output

4

Note

For the second example all the permutations are:

  * p = [1, 2, 3] : fa is equal to 1; 
  * p = [1, 3, 2] : fa is equal to 1; 
  * p = [2, 1, 3] : fa is equal to 1; 
  * p = [2, 3, 1] : fa is equal to 1; 
  * p = [3, 1, 2] : fa is equal to 0; 
  * p = [3, 2, 1] : fa is equal to 0. 



Where p is the array of the indices of initial array a. The sum of fa is equal to 4.
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
long long int exp(long long int x, long long int y) {
  if (y < 0) return 0;
  long long int ret = 1;
  for (; y; y >>= 1, x = (x * x) % mod) {
    if (y & 1) ret = (ret * x) % mod;
  }
  return ret;
}
long long int pexp(long long int x, long long int y) {
  long long int ret = 1;
  for (; y; y >>= 1, x = (x * x)) {
    if (y & 1) ret = (ret * x);
  }
  return ret;
}
long long int gcd(long long int x, long long int y) {
  if (!x || !y) return x + y;
  return x % y == 0 ? y : gcd(y, x % y);
}
long long int lcm(long long int x, long long int y) {
  return x * (y / gcd(x, y));
}
long long int bsum(long long int u, long long int b) {
  long long int ret = 0;
  if (u < b) return u;
  while (u) {
    ret += u % b;
    u /= b;
  }
  return ret;
}
long long int prival(long long int u, long long int p) {
  int cn = 0;
  while (u % p == 0) {
    cn++;
    u = u / p;
  }
  return cn;
}
long long int minv(long long int a, long long int b) {
  return 1 < a ? b - minv(b % a, a) * b / a : 1;
}
long long int extm(long long int a, long long int b) {
  long long int ret = 0;
  while (a != 0) {
    if (a % 2 == 1) {
      ret += b;
      ret %= mod;
    }
    a >>= 1;
    b = (2 * b) % mod;
  }
  return ret;
}
long long int eaphi(long long int x) {
  long long int t = x, ret = x, i;
  for (i = 2; i * i <= x; i++) {
    if (t % i == 0) {
      ret -= ret / i;
      while (t % i == 0) t /= i;
    }
  }
  if (t != 1) ret -= ret / t;
  return ret;
}
bool isprime(long long int x) {
  if (x <= 1) return false;
  for (long long int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}
long long int fac[1111111];
long long int inv[1111111];
long long int a[1111111];
vector<pair<long long int, long long int> > rd;
long long int ans, add, su;
int n;
long long int cc, ps;
int main(void) {
  cin >> n;
  int i;
  long long int x;
  for (i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    su += a[i];
    if (su >= mod) su -= mod;
  }
  sort(a + 1, a + n + 1);
  for (i = 1; i <= n; i++) {
    x = a[i];
    cc = 0;
    while (x == a[i]) {
      i++;
      cc++;
    }
    i--;
    rd.push_back(make_pair(a[i], cc));
  }
  fac[0] = 1;
  inv[1] = 1;
  fac[1] = 1;
  for (i = 2; i <= n; i++) {
    fac[i] = (fac[i - 1] * i) % mod;
    inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
  }
  cc = 0;
  reverse(rd.begin(), rd.end());
  for (i = 0; i < rd.size(); i++) {
    add = rd[i].first;
    cc += rd[i].second;
    add = (add * fac[n]) % mod;
    add = (add * rd[i].second) % mod;
    add = (add * inv[cc]) % mod;
    ans += add;
    if (ans >= mod) ans -= mod;
  }
  ans -= (rd[0].first * fac[n]) % mod;
  ans = (ans + 100 * mod) % mod;
  cout << ans;
  return 0;
}
