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>
namespace FastIO {
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE], *is = ibuf, *its = ibuf;
char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
inline char getch() {
  if (is == its) its = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
  return (is == its) ? EOF : *is++;
}
inline int getint() {
  int res = 0, neg = 0, ch = getch();
  while (!(isdigit(ch) || ch == '-') && ch != EOF) ch = getch();
  if (ch == '-') {
    neg = 1;
    ch = getch();
  }
  while (isdigit(ch)) {
    res = (res << 3) + (res << 1) + (ch - '0');
    ch = getch();
  }
  return neg ? -res : res;
}
inline void flush() {
  fwrite(obuf, 1, os - obuf, stdout);
  os = obuf;
}
inline void putch(char ch) {
  *os++ = ch;
  if (os == ot) flush();
}
inline void putint(int res) {
  static char q[10];
  if (res == 0)
    putch('0');
  else if (res < 0) {
    putch('-');
    res = -res;
  }
  int top = 0;
  while (res) {
    q[top++] = res % 10 + '0';
    res /= 10;
  }
  while (top--) putch(q[top]);
}
inline void space(bool x) {
  if (!x)
    putch('\n');
  else
    putch(' ');
}
}  // namespace FastIO
inline void read(int &x) {
  int rt = FastIO::getint();
  x = rt;
}
inline void print(int x, bool enter) {
  FastIO::putint(x);
  FastIO::flush();
  FastIO::space(enter);
}
const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;
int inv[MAXN], fac[MAXN], a[MAXN], n, ans;
inline int quick_power(int a, int b, int p = mod) {
  int res = 1, base = a;
  while (b) {
    if (b & 1) res = 1ll * res * base % p;
    b >>= 1;
    base = 1ll * base * base % p;
  }
  return res;
}
inline void init(int N = MAXN - 1) {
  fac[0] = fac[1] = 1;
  for (int i = (2); i <= (N); i += (1)) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[N] = quick_power(fac[N], mod - 2);
  for (int i = (N - 1); i >= (1); i -= (1))
    inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
inline int C(int n, int m) {
  if (m == 0 || n == m)
    return 1;
  else
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main(void) {
  scanf("%d", &n);
  init();
  for (int i = (1); i <= (n); i += (1)) scanf("%d", &a[i]);
  std::sort(a + 1, a + n + 1);
  for (int i = 1, j; i <= n;) {
    j = i;
    while (a[j + 1] == a[j]) j++;
    if (j == n) break;
    (ans += 1ll * fac[n - i] * (j - i + 1) % mod * a[i] % mod * fac[i - 1] %
            mod * C(n, n - i + 1) % mod) %= mod;
    i = j + 1;
  }
  printf("%d\n", ans);
  return 0;
}
