Expected Value of a Permutation

You are given an array of $N$ integers $A = [A_1, A_2, \cdots, A_N]$. Summing every element of $A$ is boring, so you decided to take it to the next level. A permutation $P$ of $1$ to $N$ is generated at random. Each permutation of $1$ to $N$ has an equal probability of being chosen as $P$.

You also define arrays $X_0, X_1, X_2, \ldots, X_N$ and an integer $Y$ as follows.

• $X_0 = A$
• For $1 \le i \le N$, $X_i$ is $X_{i-1}$ with every element whose index is a multiple of $i$ changed to $0$.
• $Y = \text{sum}(X_1) + \text{sum}(X_2) + \cdots + \text{sum}(X_N)$, where $\text{sum}(X_i)$ is the sum of every integer in $X_i$.

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

• $X_0 = [4, 1, 2, 3, 4]$
• $X_1 = [4, 1, 0, 3, 4]$ because $P_1 = 3$, so the 3rd element of $X_1$ becomes $0$.
• $X_2 = [4, 0, 0, 0, 4]$ because $P_2 = 2$, so the 2nd and 4th elements of $X_2$ become $0$.
• $X_3 = [4, 0, 0, 0, 4]$ because $P_3 = 4$, so the 4th element of $X_3$ becomes $0$.
• $X_4 = [0, 0, 0, 0, 0]$ because $P_4 = 1$, so every element of $X_4$ becomes $0$.
• $X_5 = [0, 0, 0, 0, 0]$ because $P_5 = 5$, so the 5th element of $X_5$ becomes $0$.

Therefore $Y = 12 + 8 + 8 + 0 + 0 = 28$ in this case.

Since $P$ is generated at random, you wonder about 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 \times D^{-1}) \bmod 1000000007$. In other words, print the unique integer $K$ ($0 \le K < 1000000007$) satisfying $C \equiv DK \pmod{1000000007}$.

The first line contains an integer $N$ ($1 \le N \le 100000$), the number of integers in $A$. The second line contains $N$ integers $A_i$ ($0 \le A_i \le 10^9$), which form the array $A$.

Print the expected value of $Y$ on one line, in the format specified in the problem description.