시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 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:

  • X0 = A
  • Xi for 1 ≤ i ≤ N is defined as Xi−1 but all integers whose indices are multiples of i are changed to 0.
  • Y = sum(X1) + sum(X2) + · · · + sum(XN), where sum(Xi) is the sum of all integers in the array Xi.

For example, if A = [4, 1, 2, 3, 4] and P = [3, 2, 4, 1, 5], then:

  • X0 = [4, 1, 2, 3, 4]
  • X1 = [4, 1, 0, 3, 4] ← P1 = 3, so, the 3rd element of X1 is changed to 0.
  • X2 = [4, 0, 0, 0, 4] ← P2 = 2, so, the 2nd and 4th elements of X2 are changed to 0.
  • X3 = [4, 0, 0, 0, 4] ← P3 = 4, so, the 4th element of X3 is changed to 0.
  • X4 = [0, 0, 0, 0, 0] ← P4 = 1, so, all elements of X4 are changed to 0.
  • X5 = [0, 0, 0, 0, 0] ← P5 = 5, so, the 5th element of X5 is changed to 0.

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.

예제 입력 1

5
4 1 2 3 4

예제 출력 1

500000020

There are 5! = 120 possible permutations for the value of P.

  • When the value of P = [3, 2, 4, 1, 5], the value of Y = 28 as described in the problem statement above.
  • When the value of P = [2, 1, 3, 4, 5], the value of Y = 10.
  • . . .

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.