#include <bits/stdc++.h>
const long long INF = 1000000001;
const long long MOD = 1000000007;
using namespace std;
vector<vector<long long>> del;
vector<long long> was, num;
long long C = 0;
long long sum_gcd_fast(vector<long long> &a, long long cnt) {
  vector<long long> all;
  for (long long q : a) {
    for (long long q1 : del[q]) {
      if (was[q1] != cnt) {
        was[q1] = cnt, num[q1] = 0;
        all.push_back(q1);
      }
      num[q1]++;
    }
  }
  for (long long q : all) {
    num[q] = num[q] * num[q];
  }
  sort(all.rbegin(), all.rend());
  long long ans = 0;
  for (long long q : all) {
    ans += num[q] * q;
    for (long long q1 : del[q]) {
      num[q1] -= num[q];
    }
  }
  return ans;
}
void prepare() {
  del.resize(C), was.assign(C, -1), num.assign(C, 0);
  for (long long q = 1; q < C; q++) {
    for (long long q1 = q; q1 < C; q1 += q) {
      del[q1].push_back(q);
    }
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long n;
  cin >> n;
  C = n + 1;
  vector<long long> a(n + 1);
  for (long long q = 1; q <= n; q++) {
    cin >> a[q];
    C = max(C, a[q] + 1);
  }
  prepare();
  vector<long long> sums(n + 1);
  long long cnt = 0;
  for (long long q = 1; q <= n; q++) {
    vector<long long> now;
    for (long long q1 = q; q1 <= n; q1 += q) {
      now.push_back(a[q1]);
    }
    sums[q] = sum_gcd_fast(now, cnt++);
  }
  long long ans = 0;
  for (long long q = n; q > 0; q--) {
    ans += sums[q] % MOD * q % MOD;
    for (long long q1 : del[q]) {
      if (q1 != q) {
        sums[q1] -= sums[q];
      }
    }
  }
  cout << ans % MOD << '\n';
  return 0;
}

### Prompt

Please formulate 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>
const long long INF = 1000000001;
const long long MOD = 1000000007;
using namespace std;
vector<vector<long long>> del;
vector<long long> was, num;
long long C = 0;
long long sum_gcd_fast(vector<long long> &a, long long cnt) {
  vector<long long> all;
  for (long long q : a) {
    for (long long q1 : del[q]) {
      if (was[q1] != cnt) {
        was[q1] = cnt, num[q1] = 0;
        all.push_back(q1);
      }
      num[q1]++;
    }
  }
  for (long long q : all) {
    num[q] = num[q] * num[q];
  }
  sort(all.rbegin(), all.rend());
  long long ans = 0;
  for (long long q : all) {
    ans += num[q] * q;
    for (long long q1 : del[q]) {
      num[q1] -= num[q];
    }
  }
  return ans;
}
void prepare() {
  del.resize(C), was.assign(C, -1), num.assign(C, 0);
  for (long long q = 1; q < C; q++) {
    for (long long q1 = q; q1 < C; q1 += q) {
      del[q1].push_back(q);
    }
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long n;
  cin >> n;
  C = n + 1;
  vector<long long> a(n + 1);
  for (long long q = 1; q <= n; q++) {
    cin >> a[q];
    C = max(C, a[q] + 1);
  }
  prepare();
  vector<long long> sums(n + 1);
  long long cnt = 0;
  for (long long q = 1; q <= n; q++) {
    vector<long long> now;
    for (long long q1 = q; q1 <= n; q1 += q) {
      now.push_back(a[q1]);
    }
    sums[q] = sum_gcd_fast(now, cnt++);
  }
  long long ans = 0;
  for (long long q = n; q > 0; q--) {
    ans += sums[q] % MOD * q % MOD;
    for (long long q1 : del[q]) {
      if (q1 != q) {
        sums[q1] -= sums[q];
      }
    }
  }
  cout << ans % MOD << '\n';
  return 0;
}

```