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: interview

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)
            
        
def __starting_point():
    main()
__starting_point()


import atexit
import io
import sys

# IO Buffering
_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[a] = P(n, a) = n!/(n-a)!
    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()

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 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(list(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)