Given a permutation $P_1, P_2, \dots, P_n$ of $1$ to $n$, calculate the sum of $P_i \cdot P_j \cdot P_k$ for all triples $(i, j, k)$ such that $1 \le i, j, k \le n$ and $\gcd(i, j) = \gcd(j, k) = \gcd(k, i) = 1$.

The answer should be taken modulo $2^{30}$.

Input

The first line contains a positive integer $n$.

The next line contains $n$ positive integers $P_1, P_2, \dots, P_n$.

Output

Output the answer.

Constraints

• $20\%$, $n \le 100$
• $40\%$, $n \le 2000$
• $100\%$, $n \le 10^5$
• Among these, $10\%$ of the test cases have $n = 10^5$ and $P_i = i$.

Examples

Input 1

5
3 4 2 5 1

Output 1

981