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;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
long long a[1000001];
const long long base = 1000000007;
long long f[1000001];
long long power(long long a, long long b) {
  if (b == 0) return 1;
  long long t = power(a, b / 2);
  t = (t * t) % base;
  if (b % 2) t = (t * a) % base;
  return t;
}
int n;
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) read(a[i]);
  sort(a + 1, a + n + 1);
  f[0] = 1;
  for (int i = (1); i <= (n); i++) f[i] = (f[i - 1] * i) % base;
  long long ans = 0;
  for (int i = (1); i <= (n); i++) {
    if (a[i] == a[n]) break;
    int l = 1, r = i - 1, m, res = 0;
    while (l <= r) {
      m = (l + r) / 2;
      if (a[m] < a[i]) {
        res = m;
        l = m + 1;
      } else
        r = m - 1;
    }
    ans = (ans + (a[i] * power(n - res, base - 2)) % base) % base;
  }
  ans = (ans * f[n]) % base;
  write(ans);
}
