16593번 - Expected Value of a Permutation

You have an array of N integers A = [A₁, A₂, · · · , A_N]. 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 X₀, X₁, X₂, ..., X_N and an integer Y as follows:

• X₀ = A
• X_i for 1 ≤ i ≤ N is defined as X_i−1 but all integers whose indices are multiples of i are changed to 0.
• Y = sum(X₁) + sum(X₂) + · · · + sum(X_N), where sum(X_i) is the sum of all integers in the array X_i.

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

• X₀ = [4, 1, 2, 3, 4]
• X₁ = [4, 1, 0, 3, 4] ← P₁ = 3, so, the 3^rd element of X₁ is changed to 0.
• X₂ = [4, 0, 0, 0, 4] ← P₂ = 2, so, the 2^nd and 4^th elements of X₂ are changed to 0.
• X₃ = [4, 0, 0, 0, 4] ← P₃ = 4, so, the 4^th element of X₃ is changed to 0.
• X₄ = [0, 0, 0, 0, 0] ← P₄ = 1, so, all elements of X₄ are changed to 0.
• X₅ = [0, 0, 0, 0, 0] ← P₅ = 5, so, the 5^th element of X₅ 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⁻¹) 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: A_i (0 ≤ A_i ≤ 10⁹) representing the array A.

Output in a line the expected value of Y using the format specified in the problem description.