You are given an array a of length n. We define f_{a} the following way:

  Initially f_{a} = 0, M = 1;  for every 2 ≤ i ≤ n if a_{M} < a_{i} then we set f_{a} = f_{a} + a_{M} and then set M = i. 

Calculate the sum of f_{a} over all n! permutations of the array a modulo 10^9 + 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 a_1, a_2, ..., a_{n} (1 ≤  a_{i} ≤  10^9).


-----Output-----

Print the only integer, the sum of f_{a} over all n! permutations of the array a modulo 10^9 + 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] : f_{a} is equal to 1;  p = [1, 3, 2] : f_{a} is equal to 1;  p = [2, 1, 3] : f_{a} is equal to 1;  p = [2, 3, 1] : f_{a} is equal to 1;  p = [3, 1, 2] : f_{a} is equal to 0;  p = [3, 2, 1] : f_{a} is equal to 0. 

Where p is the array of the indices of initial array a. The sum of f_{a} is equal to 4.

Difficulty: HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
def main():
	f = [1]
	for i in range(1, 1000002):
		f.append(f[-1] * i % 1000000007)
	n = int(input())
	a = sorted((int(x) for x in input().split()))
	sol = 0
	j = 0
	s = 1
	sq = 1
	for i in range(n - 1):
		sq = sq * (n - i) % 1000000007
		if a[i] != a[i + 1]:
			sol += a[i] * (i - j + 1) * f[n - j - 1] * s
			j = i + 1
			s = sq
	print(sol % 1000000007)
main()


import sys
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
ans = 0
mod = 10 ** 9 + 7
b = sorted(cnt.keys(), reverse=True)
m = cnt[b[0]]
for key in b[1:]:
	m += cnt[key]
	ans = (ans + pow(m, mod - 2, mod) * key * cnt[key]) % mod
for i in range(2, n + 1):
	ans = ans * i % mod
print(ans)


mod = 10 ** 9 + 7
n = int(input())
a = sorted(map(int, input().split()))
ma = max(a)
prev = -1
smaller = 0
cur = 0
total = 0
for x in a:
	if x == ma:
		continue
	if x == prev:
		cur += 1
	else:
		smaller += cur
		cur = 1
		prev = x
	total += x * pow(n - smaller, mod - 2, mod)
	total %= mod
for i in range(1, n + 1):
	total *= i
	total %= mod
print(total)


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def main():
	n = int(input())
	a = sorted((int(x) for x in input().split()))
	factorial = [1] * n
	perm_n = [1] * n
	for i in range(1, n):
		factorial[i] = factorial[i - 1] * i % 1000000007
		perm_n[i] = perm_n[i - 1] * (n - i + 1) % 1000000007
	ans = 0
	l = 0
	for i in range(n):
		if a[i] == a[-1]:
			break
		if a[i] > a[i - 1]:
			l = i
		ans += a[i] * perm_n[l] * factorial[n - l - 1]
	print(ans % 1000000007)

def __starting_point():
	main()
__starting_point()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
n = inp()
a = inpl()
a.sort()
c = Counter(a)
now = a[0]
mx = max(a)
A = 0
nn = 1
for i in range(1, n + 1):
	nn *= i
	nn %= mod
res = 0
for (i, x) in enumerate(a):
	if now != x:
		A += c[now]
		now = x
	if mx == x:
		break
	tmp = nn * x * pow(n - A, mod - 2, mod) % mod
	tmp %= mod
	res += tmp
	res %= mod
print(res)