938_E. Max History
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.
```python

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)
            
        
if __name__ == '__main__':
    main()
```