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

$$$∑_{i=1}^{n} {∑_{j=1}^{n} {\gcd(a_i, a_j) ⋅ \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) ⋅ \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 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 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
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

const int MOD = (int) 1e9 + 7;

int pwr (const int &a, const int &b)
{
    if(b == 0)
        return 1;
    if(b & 1)
        return (ll) a * pwr(a, (b ^ 1)) % MOD;
    int aux = pwr(a, (b >> 1));
    return (ll) aux * aux % MOD;
}

int f[N_MAX + 2];

vector <int> divs[N_MAX + 2];

int n;

int a[N_MAX + 2];
int cnt[N_MAX + 2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for(int i = 1; i <= N_MAX; i++)
        f[i] = i;
    for(int d = 1; d <= N_MAX; d++)
        for(int i = d; i <= N_MAX; i += d)
        {
            if(i != d)
            {
                f[i] -= f[d];
                if(f[i] < 0)
                    f[i] += MOD;
            }
            divs[i].push_back(d);
        }

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    int answer = 0;
    for(int d = 1; d <= n; d++)
    {
        int sum = 0;
        if(n / d <= 100)
        {
            for(int i = d; i <= n; i += d)
                for(int j = d; j <= n; j += d)
                {
                    sum += __gcd(a[i], a[j]);
                    if(sum >= MOD)
                        sum -= MOD;
                }
        }
        else
        {
            for(int i = d; i <= n; i += d)
                for(int g : divs[a[i]])
                    cnt[g]++;

            for(int i = d; i <= n; i += d)
                for(int g : divs[a[i]])
                {
                    sum = (sum + (ll) f[g] * cnt[g]) % MOD;
                    cnt[g] = 0;
                }
        }

        answer = (answer + sum % MOD * f[d]) % MOD;
    }

    cout << answer << "\n";

    return 0;
}
