시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 2 | 2 | 100.000% |
You have an array of N integers A = [A1, A2, · · · , AN]. Summing all integers in A is boring, so you decided to take it to the next level. You have a permutation P of 1 to N generated randomly. Each permutation from 1 to N has an equal probability to be chosen as P.
You also want to define arrays X0, X1, X2, ..., XN and an integer Y as follows:
For example, if A = [4, 1, 2, 3, 4] and P = [3, 2, 4, 1, 5], then:
Therefore, Y = 12 + 8 + 8 + 0 + 0 = 28 in this case.
Since P is generated randomly, you are wondering the expected value of Y . Let C/D be the expected value of Y where C and D are relatively prime non-negative integers. Print the value of (C ×D−1) mod 1000000007. In other words, you must print the value of the unique integer K (0 ≤ K < 1000000007) satisfying C ≡ DK (mod 1000000007).
Input begins with an integer N (1 ≤ N ≤ 100000) representing the number of integers in A. The second line contains N integers: Ai (0 ≤ Ai ≤ 109) representing the array A.
Output in a line the expected value of Y using the format specified in the problem description.
5 4 1 2 3 4
500000020
There are 5! = 120 possible permutations for the value of P.
The sum of Y for all possible values of P is 1980. Therefore, the expected value of Y is 1980/120 = 33/2. Since 33 ≡ 2 × 500000020 (mod 1000000007), you must print 500000020 for this sample case.