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;
string DBG_DLM(int &i) { return (i++ == 0 ? "" : ", "); }
template <class T>
ostream &operator<<(ostream &os, vector<T> v);
template <class T>
ostream &operator<<(ostream &os, set<T> v);
template <class T>
ostream &operator<<(ostream &os, queue<T> q);
template <class T>
ostream &operator<<(ostream &os, priority_queue<T> q);
template <class T, class K>
ostream &operator<<(ostream &os, pair<T, K> p);
template <class T, class K>
ostream &operator<<(ostream &os, map<T, K> mp);
template <class T, class K>
ostream &operator<<(ostream &os, unordered_map<T, K> mp);
template <int I, class TPL>
void DBG(ostream &os, TPL t) {}
template <int I, class TPL, class H, class... Ts>
void DBG(ostream &os, TPL t) {
  os << (I == 0 ? "" : ", ") << get<I>(t);
  DBG<I + 1, TPL, Ts...>(os, t);
}
template <class T, class K>
void DBG(ostream &os, pair<T, K> p, string delim) {
  os << "(" << p.first << delim << p.second << ")";
}
template <class... Ts>
ostream &operator<<(ostream &os, tuple<Ts...> t) {
  os << "(";
  DBG<0, tuple<Ts...>, Ts...>(os, t);
  os << ")";
  return os;
}
template <class T, class K>
ostream &operator<<(ostream &os, pair<T, K> p) {
  DBG(os, p, ", ");
  return os;
}
template <class T>
ostream &operator<<(ostream &os, vector<T> v) {
  {
    int i = 0;
    os << "{";
    {
      for (auto &&t : v) {
        os << DBG_DLM(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream &operator<<(ostream &os, set<T> s) {
  {
    int i = 0;
    os << "{";
    {
      for (auto &&t : s) {
        os << DBG_DLM(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream &operator<<(ostream &os, queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << DBG_DLM(i) << q.front();
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream &operator<<(ostream &os, priority_queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << DBG_DLM(i) << q.top();
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
ostream &operator<<(ostream &os, map<T, K> m) {
  {
    int i = 0;
    os << "{";
    {
      for (auto &&p : m) {
        os << DBG_DLM(i);
        DBG(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
ostream &operator<<(ostream &os, unordered_map<T, K> m) {
  {
    int i = 0;
    os << "{";
    {
      for (auto &&p : m) {
        os << DBG_DLM(i);
        DBG(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vs = vector<string>;
using vvs = vector<vs>;
using vvvs = vector<vvs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vvvpii = vector<vvpii>;
template <class A, class B>
bool amax(A &a, const B &b) {
  return b > a ? a = b, 1 : 0;
}
template <class A, class B>
bool amin(A &a, const B &b) {
  return b < a ? a = b, 1 : 0;
}
ll ri() {
  ll l;
  cin >> l;
  return l;
}
string rs() {
  string s;
  cin >> s;
  return s;
}
const int mod = 1e9 + 7;
template <int MOD>
struct Mint {
  int x;
  Mint() : x(0) {}
  Mint(int y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}
  Mint(int64_t sll) : x(sll % MOD) {
    if (x < 0) x += MOD;
  }
  Mint &operator+=(const Mint &rhs) {
    if ((x += rhs.x) >= MOD) x -= MOD;
    return *this;
  }
  Mint &operator-=(const Mint &rhs) {
    if ((x += MOD - rhs.x) >= MOD) x -= MOD;
    return *this;
  }
  Mint &operator*=(const Mint &rhs) {
    x = 1LL * x * rhs.x % MOD;
    return *this;
  }
  Mint &operator/=(const Mint &rhs) {
    x = (1LL * x * rhs.inv().x) % MOD;
    return *this;
  }
  Mint operator-() const { return Mint(-x); }
  Mint operator+(const Mint &rhs) const { return Mint(*this) += rhs; }
  Mint operator-(const Mint &rhs) const { return Mint(*this) -= rhs; }
  Mint operator*(const Mint &rhs) const { return Mint(*this) *= rhs; }
  Mint operator/(const Mint &rhs) const { return Mint(*this) /= rhs; }
  bool operator<(const Mint &rhs) const { return x < rhs.x; }
  Mint inv() const {
    assert(x != 0);
    signed a = x, b = MOD, u = 1, v = 0, t;
    while (b) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return Mint(u);
  }
  Mint operator^(uint64_t t) const {
    Mint e = *this, res = 1;
    for (; t; e *= e, t >>= 1)
      if (t & 1) res *= e;
    return res;
  }
};
template <int MOD>
ostream &operator<<(ostream &os, const Mint<MOD> &rhs) {
  return os << rhs.x;
}
template <int MOD>
istream &operator>>(istream &is, Mint<MOD> &rhs) {
  int64_t s;
  is >> s;
  rhs = Mint<MOD>(s);
  return is;
};
using mint = Mint<mod>;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
const int SET_FACT_MAX = 1000006;
mint fact[SET_FACT_MAX];
mint revFact[SET_FACT_MAX];
void setFact() {
  const int N = SET_FACT_MAX;
  fact[0] = 1;
  for (int i = 1; i < N; i++) {
    fact[i] = fact[i - 1] * i;
  }
  revFact[N - 1] = fact[N - 1] ^ (mod - 2);
  for (int i = N - 2; i >= 0; i--) {
    revFact[i] = revFact[i + 1] * (i + 1);
  }
}
mint nPr(int n, int r) { return n >= r ? fact[n] * revFact[n - r] : 0; }
mint nCr(int n, int r) { return nPr(n, r) * revFact[r]; }
mint nHr(int n, int r) { return n == 0 && r == 0 ? 1 : nCr(n + r - 1, r); }
const int SET_INVMOD_MAX = 1000006;
mint invmod[SET_INVMOD_MAX];
void setInvMod() {
  invmod[1] = 1;
  for (int i = 2; i < SET_INVMOD_MAX; i++) {
    invmod[i] = invmod[mod % i] * (mod - mod / i);
  }
}
mint solve() {
  setFact();
  setInvMod();
  int n = ri();
  vector<int> A(n);
  for (int i = int(0); i < int(n); ++i) A[i] = ri();
  sort((A).begin(), (A).end());
  mint ans = 0;
  for (auto &&a : A) {
    if (a == A.back()) break;
    int cl = lower_bound((A).begin(), (A).end(), a) - A.begin();
    mint times = fact[n] * invmod[n - cl];
    ;
    ans += times * a;
  }
  return ans;
}
void Main() { cout << solve() << endl; }
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  Main();
  return 0;
}
