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.*;

public class MainB
{

    static int mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    public static void main(String[] args)
    {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);            
        
        int n = in.nextInt();
        long[] f = new long[n + 1];
        f[0] = 1;
        for(int i = 1; i <= n; i++)
            f[i] = (f[i - 1] * i) % mod;
        long[] a = in.nextLongArray(n);
        a = radixSort(a);
        int c = 1;
        for(int i = 1; i < n; i++){
            if(a[i] == a[i - 1]) continue;
            c++;
        }
        long[][] b = new long[c][2];
        b[0][0] = a[0];
        b[0][1] = 1;
        c = 0;
        for(int i = 1; i < n; i++){
            if(a[i] == a[i - 1]) b[c][1]++;
            else{
                c++;
                b[c][0] = a[i];
                b[c][1] = 1;
            }
        }
        long[] inv = new long[n + 1];
        inv[1] = 1;

        for(int i = 2; i <= n; i++) {
            inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
        }
        long res = 0;
        c = 0;
        for(int i = 0; i < b.length - 1; i++){
            long tmp = (b[i][1] * inv[n - c]);
            tmp = (tmp * (b[i][0])) % mod;
            c += b[i][1];
            res = (res + (tmp * f[n]) % mod) % mod;
        }
        out.println(res);
        
        out.close();

    }
    
    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }

    public static long[] radixSort(long[] f){ return radixSort(f, f.length); }
    
    public static long[] radixSort(long[] f, int n)
    {
            long[] to = new long[n];
            {
                    int[] b = new int[65537];
                    for(int i = 0;i < n;i++)b[1+(int)(f[i]&0xffff)]++;
                    for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
                    for(int i = 0;i < n;i++)to[b[(int)(f[i]&0xffff)]++] = f[i];
                    long[] d = f; f = to;to = d;
            }
            {
                    int[] b = new int[65537];
                    for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>16&0xffff)]++;
                    for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
                    for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>16&0xffff)]++] = f[i];
                    long[] d = f; f = to;to = d;
            }
            {
                    int[] b = new int[65537];
                    for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>32&0xffff)]++;
                    for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
                    for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>32&0xffff)]++] = f[i];
                    long[] d = f; f = to;to = d;
            }
            {
                    int[] b = new int[65537];
                    for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>48&0xffff)]++;
                    for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
                    for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>48&0xffff)]++] = f[i];
                    long[] d = f; f = to;to = d;
            }
            return f;
    }
    
    static class Pair implements Comparable<Pair>
    {

        int x,y,i,t;
        
        
        Pair (int x,int y,int i, int t)
        {
		this.x = x;
                this.y = y;
                this.i = i;
                this.t = t;
	}
        
	public int compareTo(Pair o)
        {
            return Integer.compare(this.x,o.x);
		//return 0;
	}

        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString()
        {
            return x + " "+ y + " "+ i + " "+t;
        }
        
        public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 

    static long gcd(long x, long y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

    static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

    static long pow(long n, long p, long m) {
        long result = 1;
        if (p == 0) {
            return 1;
        }

        while (p != 0) {
            if (p % 2 == 1) {
                result *= n;
            }
            if (result >= m) {
                result %= m;
            }
            p >>= 1;
            n *= n;
            if (n >= m) {
                n %= m;
            }
        }
        return result;
    }

    static long pow(long n, long p) {
        long result = 1;
        if (p == 0) {
            return 1;
        }

        while (p != 0) {
            if (p % 2 == 1) {
                result *= n;
            }
            p >>= 1;
            n *= n;
        }
        return result;
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }

        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }

        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }

    }
}    
