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.*;
import java.math.*;
import java.util.concurrent.*;

public final class max_history
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static long mod=(long)(1e9+7);
	static int[] fact;
	static int maxn=(int)(1e6+6);
	static int[] val;
	
	static int add(long a,long b)
	{
		long ret=a+b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int mul(long a,long b)
	{
		long ret=a*b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static void build()
	{
		fact=new int[maxn];fact[0]=1;

		for(int i=1;i<maxn;i++)
		{
			fact[i]=mul(fact[i-1],i);
		}
	}
	
	static void shuffle(int[] a)
	{	
		for(int i=0;i<a.length;i++)
		{
			int next=rnd.nextInt(a.length);
			
			int temp=a[i];a[i]=a[next];a[next]=temp;
		}
	}
	
	static int pow(long a,long b)
	{
		long x=1,y=a;
		
		while(b>0)
		{	
			if(b%2==1)
			{
				x=mul(x,y);
			}
			
			y=mul(y,y);b=b/2;
		}
		
		return (int)(x%mod);
	}
	
    public static void main(String args[]) throws Exception
    {
		build();
		
		int n=sc.nextInt();int[] a=new int[n];int max=-1;
		
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
			
			max=Math.max(max,a[i]);
		}
		
		shuffle(a);Arrays.sort(a);
		
		int res=0;
		
		for(int i=n-1;i>=0;i--)
		{
			int ctr=1;
			
			while(i>=1 && a[i]==a[i-1])
			{
				i--;ctr++;
			}
			
			int now=mul(a[i],ctr);
			
			if(a[i]<max)
			{	
				int num=fact[n],den=pow(n-i,mod-2);
				
				//out.println(num+" "+den);
				
				int mul=mul(num,den);
				
				//out.println(mul);
				
				mul=mul(mul,now);
				
				res=add(res,mul);
			}
		}
		
		out.println(res);out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}