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;
const long long int modulo = 1000 * 1000 * 1000 + 7;
long long int* factors = new long long int[1000 * 1000 + 1000];
long long int* sus = new long long int[1000 * 1000 + 1000];
long long int fact(long long int k) {
  if (factors[k] != -1) return factors[k];
  factors[k] = (fact(k - 1) * k) % modulo;
  return factors[k];
}
long long int reverseElem(long long int a, long long int m = modulo) {
  long long int q, r, x1, x2, y1, y2, x, d, y, b;
  b = m;
  if (b == 0) {
    d = a;
    x = 1;
    y = 0;
  } else {
    x2 = 1, x1 = 0, y2 = 0, y1 = 1;
    while (b > 0) {
      q = a / b;
      r = a - q * b;
      x = x2 - q * x1;
      y = y2 - q * y1;
      a = b;
      b = r;
      x2 = x1;
      x1 = x;
      y2 = y1;
      y1 = y;
    }
    d = a;
    x = x2;
    y = y2;
  }
  if (d != 1) return -1;
  return (x % m + m) % m;
}
long long int su(long long int k) {
  if (sus[k] != -1) return sus[k];
  sus[k] = (su(k - 1) * k + 1) % modulo;
  return sus[k];
}
int main() {
  for (int i = 0; i < 1000 * 1000 + 1000; i++) factors[i] = -1;
  factors[0] = 1;
  for (int i = 0; i < 1000 * 1000 + 1000; i++) sus[i] = -1;
  sus[0] = 1;
  ios::sync_with_stdio(0);
  int n;
  cin >> n;
  int* a = new int[n];
  map<int, int> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    m[a[i]]++;
  }
  long long int s = 0;
  long long int ans = 0;
  for (auto it = m.begin(); it != m.end(); it++) {
    if (s + it->second == n) break;
    ans += ((fact(n) * reverseElem(n - s)) % modulo *
            ((it->first) * (it->second) % modulo)) %
           modulo;
    ans %= modulo;
    s += it->second;
  }
  cout << ans;
  return 0;
}
