#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MOD = (int)1e9 + 7;
long long n, a[MAXN], sum_gcd[MAXN], mobius[MAXN], euler[MAXN], nxt[MAXN],
    cnt[MAXN];
long long sum;
vector<long long> divisor[MAXN];
long long add(long long &a, long long b) { a = (a + b) % MOD; }
long long sub(long long &a, long long b) { a = (((a - b) % MOD) + MOD) % MOD; }
void update(int x, int val) {
  for (int d : divisor[x]) {
    sub(sum, euler[d] * cnt[d] * cnt[d]);
    cnt[d] += val;
    add(sum, euler[d] * cnt[d] * cnt[d]);
  }
}
int main() {
  for (int i = 1; i < MAXN; ++i)
    for (int j = i; j < MAXN; j += i) divisor[j].push_back(i);
  for (int i = 2; i < MAXN; ++i) {
    for (int j = i; j < MAXN; j += i) {
      if (nxt[j] == 0) nxt[j] = i;
    }
  }
  mobius[1] = 1;
  euler[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    int p = nxt[i];
    if (p == nxt[i / p]) {
      mobius[i] = 0;
      euler[i] = euler[i / p] * p;
    } else {
      mobius[i] = -mobius[i / p];
      euler[i] = euler[i / p] * (p - 1);
    }
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int k = 1; k <= n; ++k) {
    for (int i = k; i <= n; i += k)
      for (auto d : divisor[a[i]]) cnt[d] += 1;
    for (int i = k; i <= n; i += k)
      for (auto d : divisor[a[i]]) {
        add(sum_gcd[k], euler[d] * cnt[d] * cnt[d]);
        cnt[d] = 0;
      }
  }
  long long ans = 0;
  for (int k = 1; k <= n; ++k) {
    add(ans, euler[k] * sum_gcd[k]);
  }
  cout << ans;
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MOD = (int)1e9 + 7;
long long n, a[MAXN], sum_gcd[MAXN], mobius[MAXN], euler[MAXN], nxt[MAXN],
    cnt[MAXN];
long long sum;
vector<long long> divisor[MAXN];
long long add(long long &a, long long b) { a = (a + b) % MOD; }
long long sub(long long &a, long long b) { a = (((a - b) % MOD) + MOD) % MOD; }
void update(int x, int val) {
  for (int d : divisor[x]) {
    sub(sum, euler[d] * cnt[d] * cnt[d]);
    cnt[d] += val;
    add(sum, euler[d] * cnt[d] * cnt[d]);
  }
}
int main() {
  for (int i = 1; i < MAXN; ++i)
    for (int j = i; j < MAXN; j += i) divisor[j].push_back(i);
  for (int i = 2; i < MAXN; ++i) {
    for (int j = i; j < MAXN; j += i) {
      if (nxt[j] == 0) nxt[j] = i;
    }
  }
  mobius[1] = 1;
  euler[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    int p = nxt[i];
    if (p == nxt[i / p]) {
      mobius[i] = 0;
      euler[i] = euler[i / p] * p;
    } else {
      mobius[i] = -mobius[i / p];
      euler[i] = euler[i / p] * (p - 1);
    }
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int k = 1; k <= n; ++k) {
    for (int i = k; i <= n; i += k)
      for (auto d : divisor[a[i]]) cnt[d] += 1;
    for (int i = k; i <= n; i += k)
      for (auto d : divisor[a[i]]) {
        add(sum_gcd[k], euler[d] * cnt[d] * cnt[d]);
        cnt[d] = 0;
      }
  }
  long long ans = 0;
  for (int k = 1; k <= n; ++k) {
    add(ans, euler[k] * sum_gcd[k]);
  }
  cout << ans;
  return 0;
}

```