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