순열의 기댓값

정수 배열 $A = [A_1, A_2, \cdots, A_N]$이 주어진다. $A$의 모든 원소를 더하는 일은 지루해서, 당신은 한 단계 더 나아가기로 했다. $1$부터 $N$까지의 순열 $P$가 무작위로 만들어진다. $1$부터 $N$까지의 각 순열은 같은 확률로 $P$로 선택된다.

또한 배열 $X_0, X_1, X_2, \ldots, X_N$과 정수 $Y$를 다음과 같이 정의한다.

• $X_0 = A$
• $1 \le i \le N$인 $i$에 대해 $X_i$는 $X_{i-1}$에서 인덱스가 $i$의 배수인 모든 원소를 $0$으로 바꾼 배열이다.
• $Y = \text{sum}(X_1) + \text{sum}(X_2) + \cdots + \text{sum}(X_N)$이며, $\text{sum}(X_i)$는 배열 $X_i$의 모든 정수의 합이다.

예를 들어 $A = [4, 1, 2, 3, 4]$이고 $P = [3, 2, 4, 1, 5]$이면:

• $X_0 = [4, 1, 2, 3, 4]$
• $X_1 = [4, 1, 0, 3, 4]$ ← $P_1 = 3$이므로 $X_1$의 3번째 원소가 $0$으로 바뀐다.
• $X_2 = [4, 0, 0, 0, 4]$ ← $P_2 = 2$이므로 $X_2$의 2번째와 4번째 원소가 $0$으로 바뀐다.
• $X_3 = [4, 0, 0, 0, 4]$ ← $P_3 = 4$이므로 $X_3$의 4번째 원소가 $0$으로 바뀐다.
• $X_4 = [0, 0, 0, 0, 0]$ ← $P_4 = 1$이므로 $X_4$의 모든 원소가 $0$으로 바뀐다.
• $X_5 = [0, 0, 0, 0, 0]$ ← $P_5 = 5$이므로 $X_5$의 5번째 원소가 $0$으로 바뀐다.

따라서 이 경우 $Y = 12 + 8 + 8 + 0 + 0 = 28$이다.

$P$가 무작위로 만들어지므로, 당신은 $Y$의 기댓값이 궁금해졌다. $Y$의 기댓값을 $C/D$라 하자. 여기서 $C$와 $D$는 서로소인 음이 아닌 정수이다. $(C \times D^{-1}) \bmod 1000000007$을 출력하라. 즉, $C \equiv DK \pmod{1000000007}$을 만족하는 유일한 정수 $K$ ($0 \le K < 1000000007$)를 출력해야 한다.

첫 줄에 $A$에 들어 있는 정수의 개수를 나타내는 정수 $N$ ($1 \le N \le 100000$)이 주어진다. 둘째 줄에 배열 $A$를 나타내는 정수 $A_i$ ($0 \le A_i \le 10^9$) $N$개가 주어진다.

문제 설명에서 정한 형식으로 $Y$의 기댓값을 한 줄에 출력한다.