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 gcd(long long a, long long b) {
  while (b != 0) {
    a = a % b;
    swap(a, b);
  }
  return a;
}
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1;
  long long ans = extend_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return ans;
}
long long inverse(long long a) {
  long long x, y;
  extend_gcd((1000 * 1000 * 1000 + 7), a, x, y);
  y %= (1000 * 1000 * 1000 + 7);
  y += (1000 * 1000 * 1000 + 7);
  y %= (1000 * 1000 * 1000 + 7);
  return y;
}
long long dp[1234567], cnt[1234567];
long long counter = 0;
map<long long, long long> mapi, inv;
map<long long, long long>::iterator it;
long long a[1234567];
int main() {
  std::ios::sync_with_stdio(false);
  long long n, i;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    mapi[a[i]] = 0;
  }
  for (it = mapi.begin(); it != mapi.end(); it++) {
    it->second = counter++;
    inv[it->second] = it->first;
  }
  for (i = 0; i < n; i++) {
    cnt[mapi[a[i]]]++;
  }
  dp[counter - 1] = 0;
  long long ans = 0;
  long long wow = 0;
  long long elems = cnt[counter - 1];
  for (i = counter - 2; i >= 0; i--) {
    dp[i] = ans;
    dp[i] *= inverse(elems);
    dp[i] %= (1000 * 1000 * 1000 + 7);
    dp[i] += inv[i];
    dp[i] %= (1000 * 1000 * 1000 + 7);
    wow += cnt[i] * dp[i];
    wow %= (1000 * 1000 * 1000 + 7);
    elems += cnt[i];
    ans += dp[i] * cnt[i];
    ans %= (1000 * 1000 * 1000 + 7);
  }
  for (i = 1; i < n; i++) {
    wow *= i;
    wow %= (1000 * 1000 * 1000 + 7);
  }
  cout << wow << endl;
  return 0;
}
