G. GCD Festival
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Mr. Chanek has an array $$$a$$$ of $$$n$$$ integers. The prettiness value of $$$a$$$ is denoted as:

$$$$$$\sum_{i=1}^{n} {\sum_{j=1}^{n} {\gcd(a_i, a_j) \cdot \gcd(i, j)}}$$$$$$

where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

In other words, the prettiness value of an array $$$a$$$ is the total sum of $$$\gcd(a_i, a_j) \cdot \gcd(i, j)$$$ for all pairs $$$(i, j)$$$.

Help Mr. Chanek find the prettiness value of $$$a$$$, and output the result modulo $$$10^9 + 7$$$!

Input

The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

Output

Output an integer denoting the prettiness value of $$$a$$$ modulo $$$10^9 + 7$$$.

Example
Input
5
3 6 2 1 4
Output
77