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.
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class E {
    public static void main(String[] args) throws Exception {
        int MOD = 1000000007;
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // Scanner scan = new Scanner(System.in);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(bf.readLine());
        Integer[] a = new Integer[n];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i=0; i<n; i++)
          a[i] = Integer.parseInt(st.nextToken());
        int[] factorial = new int[1000001];
        factorial[0] = 1;
        for(int i=1; i<1000001; i++)
          factorial[i] = (int)(1L*factorial[i-1]*i % MOD);

        Arrays.sort(a);
        long ans = 0;
        int cur_less = 0;

        for(int i=0; i<n; i++) {
          if(i > 0)
            if((int)a[i] >(int)a[i-1])
              cur_less = i;
          ans += (int)((1L*factorial[n]*exp(n-cur_less, MOD-2, MOD) % MOD)*((int)a[i]) % MOD);
        }
        ans = ans + (((1L*(MOD-1)*factorial[n])%MOD)*((int)a[n-1])) % MOD;
        ans %= MOD;
        out.println(ans);
        // StringTokenizer st = new StringTokenizer(bf.readLine());
        // int n =  Integer.parseInt(st.nextToken());


        out.close(); System.exit(0);
    }

    public static int exp(int base, int e, int mod) {
      if(e == 0) return 1;
      if(e == 1) return base;
      int val = exp(base, e/2, mod);
      int ans = (int)(1L*val*val % mod);
      if(e % 2 == 1)
        ans = (int)(1L*ans*base % mod);
      return ans;
    }


}
