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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static final long MOD = (long) 1E9 + 7;
	public static int N;
	public static long[] array;

	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(f.readLine());
		array = new long[N + 1];
		StringTokenizer st = new StringTokenizer(f.readLine());
		for (int i = 0; i < N; i++) {
			array[i] = Long.parseLong(st.nextToken());
		}
		array[N] = Long.MAX_VALUE;
		Arrays.sort(array);
		long factorial = 1;
		for (int i = 1; i <= N; i++) {
			factorial *= i;
			factorial %= MOD;
		}
		int index = 0;
		long res = 0;
		while (index < N) {
			int start = index;
			while (array[start] == array[index]) {
				index++;
			}
			if (index < N) {
				res += (((factorial * qpow(N - start, MOD - 2) % MOD) * (index - start) % MOD) * array[start] % MOD);
				res %= MOD;
			}
		}
		System.out.println(res);
	}

	public static long qpow(long a, long b) {
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1) {
				res *= a;
				res %= MOD;
			}
			a *= a;
			a %= MOD;
			b >>= 1;
		}
		return res;
	}
}