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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
function<void(void)> ____ = []() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
};
template <typename T>
vector<T> &operator<<(vector<T> &__container, T x) {
  __container.push_back(x);
  return __container;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &__container) {
  for (T _ : __container) out << _ << ' ';
  return out;
}
const int MAXN = 1e6 + 7;
const int MOD = 1e9 + 7;
int fac[MAXN], inv[MAXN], rfac[MAXN], A[MAXN], cnt[MAXN];
int sum[MAXN];
int C(int n, int m) { return 1ll * fac[n] * rfac[m] % MOD * rfac[n - m] % MOD; }
void solve() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  vector<int> vec(n);
  for (int i = 0; i < n; i++) vec[i] = A[i + 1];
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for (int i = 1; i <= n; i++)
    A[i] = lower_bound(vec.begin(), vec.end(), A[i]) - vec.begin();
  for (int i = 1; i <= n; i++) cnt[A[i]]++;
  for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
  int maxx = vec.size() - 1;
  int ret = 0;
  for (int i = 1; i <= n; i++) {
    if (A[i] == maxx) continue;
    int s = cnt[A[i] - 1];
    ret = (ret +
           1ll * vec[A[i]] * fac[n - s - 1] % MOD * fac[s] % MOD * C(n, s)) %
          MOD;
  }
  cout << ret << "\n";
}
int main() {
  fac[0] = rfac[0] = inv[1] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
  for (int i = 2; i < MAXN; i++)
    inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i < MAXN; i++) rfac[i] = 1ll * rfac[i - 1] * inv[i] % MOD;
  solve();
  return 0;
}
