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.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
         class pair{
          long n,f;pair(long a,long b){n=a;f=b;}
         }
         int a[];ArrayList<pair> al;
         long mod=(long)(1E9)+7;
         int max=(int)(1E6);
         long pre(int n){
          long r=1;
          for(int i=1;i<=n;i++)r=(i*r)%mod;
          return r;
         }
         long rpe(long a,long b){
          long ans=1;
          while(b!=0){
           if((b&1)==1)ans=(ans*a)%mod;
           a=(a*a)%mod;b>>=1;
          }return ans;
         }
        int[] radixSort(int[] f){ return radixSort(f, f.length); }
	int[] radixSort(int[] f, int n)
	{
		int[] to = new int[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]&0xffff]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		return f;
	}
         public void solve(int testNumber, InputReader in, PrintWriter out) {
             int n=in.nextInt();
             a=new int[n];
             long fac=pre(n);
             for(int i=0;i<n;i++)a[i]=in.nextInt();
             a=radixSort(a);
             al=new ArrayList<>();
             long p=a[0],f=0;
             for(int i=0;i<n;i++){
              if(a[i]==p)++f;
              else{
                al.add(new pair(p,f));p=a[i];f=1;
              }
             }al.add(new pair(p,f));
             long sum=al.get(al.size()-1).f;long ans=0;
             for(int i=al.size()-2;i>=0;i--){
               sum+=al.get(i).f;    
               ans=(ans+(((rpe(sum,mod-2)*al.get(i).f)%mod)*al.get(i).n)%mod)%mod;
               //System.out.println(ans);
             }out.print((ans*fac)%mod);
         }
    }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {    
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}   