You are given an array a of length n. We define f_{a} the following way:
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.
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}).
Print the only integer, the sum of f_{a} over all n! permutations of the array a modulo 10^{9} + 7.
2
1 3
1
3
1 1 2
4
For the second example all the permutations are:
Where p is the array of the indices of initial array a. The sum of f_{a} is equal to 4.
Name |
---|