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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class q5 {
	static ArrayList<Integer>[] gph;
	static HashMap<Integer,Long>[] gph2;
	static int[] visited,deg;
	 
	
	static long modPow(long a, long b, long mod) {
		a%=mod;
		long res=1;
		while(b>0) {
			if((b&1)==1) {
				res*=a;
				res%=mod;
			}
			b=b>>1;
			a*=a;
			a%=mod;
		}
		
		return res;
	}
	
	public static void main(String[] args) throws IOException {
		
		Reader.init(System.in);
		PrintWriter out=new PrintWriter(System.out);
		StringBuffer output=new StringBuffer("");
		int n=Reader.nextInt();
		ArrayList<Long> arr=new ArrayList<Long>();
		long[] fact=new long[n+1];
		fact[0]=1;
		long mod=(long)1e9+7;
		for(int i=1;i<=n;i++) {
			fact[i]=i*fact[i-1];
			fact[i]%=mod;
		}
		for(int i=0;i<n;i++) {
			arr.add(Reader.nextLong());
		}
		Collections.sort(arr);
		ArrayList<NoD> a2=new ArrayList<NoD>();
		NoD a=new NoD(arr.get(0),1);
		for(int i=1;i<n;i++) {
			if(arr.get(i)==a.a) {
				a.b++;
			}
			else {
				a2.add(a);
				a=new NoD(arr.get(i),1);
			}
		}
		a2.add(a);
		long ans=0;
		long smaller=0;
		for(int i=0;i<a2.size()-1;i++) {
			a=a2.get(i);
			long v=fact[n];
			v*=q5.modPow(n-smaller, mod-2, mod);
			v%=mod;
			v*=a.a;
			v%=mod;
			v*=a.b;
			v%=mod;
			
			smaller+=a.b;
			ans+=v;
			ans%=mod;
		}
		output.append(ans);
		
		out.write(output.toString());
		out.flush();
		
	}
}
class NoD{
	long a,b;;
	String s;
	
	NoD(long aa,long bb){
		a=aa;b=bb;
		s=a+" "+b;
		
	}
	@Override
	public boolean equals(Object o) {
		if(o!=null && o.getClass()==getClass()) {
			NoD c= (NoD) o;
			return c.a==a && c.b==b;
		}
		return false;
	}
	@Override
	public int hashCode() {
		return s.hashCode();
	}
}

class DisJoint{
	 int[] parent,rank;
	 DisJoint(int n){
		 parent=new int[n+1];
		 rank=new int[n+1];
		 for(int i=1;i<=n;i++) {
			 rank[i]=0;
			 parent[i]=i;
		 }
	 }
	void union(int a, int b) {
		int p1=find(a);
		int p2=find(b);
		if(p1!=p2) {
			if(rank[p1]>=rank[p2]) {
				parent[p2]=p1;
				if(rank[p1]==rank[p2]) rank[p1]++;
			}
			else {
				parent[p1]=p2;
			}
		}
	}
	
	int find(int a) {
		if(a!=parent[a]) {
			parent[a]=find(parent[a]);
		}
		return parent[a];
	}
}

//class Seg{
//	ArrayList<Integer> arr;
//	int[] segtree;
//	Seg(ArrayList<Integer> a){
//		arr=a;
//		int n=arr.size();
//		segtree=new int[4*n+1];
//	}
//	
//	void build(int index, int l, int r) {
//		if(l==r) {
//			segtree[index]=q5.occurance[arr.get(l)];
//		}
//		else {
//			int middle=(l+r)/2;
//			build(2*index+1,l,middle);
//			build(2*index+2,middle+1,r);
//			segtree[index]=Math.min(segtree[2*index+1], segtree[2*index+2]);
//		}
//	}
//	
//	int query(int index, int l, int r, int ql, int qr) {
//		if(ql<=l && r<=qr) {
//			return segtree[index];
//		}
//		else if(qr<l || ql>r) {
//			return Integer.MAX_VALUE;
//		}
//		else {
//			int middle=(l+r)/2;
//			int left=query(2*index+1,l,middle,ql,qr);
//			int right=query(2*index+2,middle+1,r,ql,qr);
//			return Math.min(left, right);
//		}
//	}
//}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    static String nextLine() throws IOException{
    	return reader.readLine();
    }
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
    
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}




 
 

 