#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 200010;
long long t, n, cnt, x, m, a[maxn], b[4 * maxn], tag[4 * maxn], ans, pos,
    c[maxn], l, r, mid, y, z, mx, k, mod = 1000000007, cnt1, cnt2, cnt3, cnt4,
                                     cnt5, cnt6, mn, vis[maxn], sum, pos1, pos2,
                                     dis[maxn];
long long dif[maxn];
long long tw[60], av, h;
double probability = 0;
set<long long> se;
vector<long long> v[maxn], gr[maxn], v1, v2, divv[maxn];
string s, s1, s2, s3, s4;
char cc[405][405], abc[205];
pair<long long, long long> p[maxn], pp;
map<long long, long long> mp;
char ch;
long long fpow(long long x, long long y) {
  if (y == 0) {
    return 1 % mod;
  }
  long long a = x % mod;
  long long a2 = 1 % mod;
  while (y > 1) {
    if (y % 2) {
      a2 *= a;
      a2 %= mod;
    }
    a *= a;
    a %= mod;
    y /= 2;
  }
  return (a * a2) % mod;
}
void build(long long l, long long r, long long v) {
  if (l == r) {
    b[v] = 0;
    return;
  }
  long long mid = (l + r) >> 1;
  build(l, mid, v << 1);
  build(mid + 1, r, v << 1 | 1);
  b[v] = 0;
}
long long qu(long long l, long long r, long long v, long long l2,
             long long r2) {
  if (l == l2 && r == r2) {
    return b[v];
  }
  tag[v << 1] += tag[v];
  b[v << 1] *= tw[tag[v]];
  b[v << 1] %= mod;
  tag[v << 1 | 1] += tag[v];
  b[v << 1 | 1] *= tw[tag[v]];
  b[v << 1 | 1] %= mod;
  tag[v] = 0;
  long long mid = (l + r) >> 1;
  if (mid >= r2) {
    return qu(l, mid, v << 1, l2, r2);
  } else if (mid + 1 <= l2) {
    return qu(mid + 1, r, v << 1 | 1, l2, r2);
  } else {
    return (qu(l, mid, v << 1, l2, mid) +
            qu(mid + 1, r, v << 1 | 1, mid + 1, r2)) %
           mod;
  }
}
void modify1(long long l, long long r, long long v, long long l2, long long r2,
             long long m) {
  if (l == l2 && r == r2) {
    b[v] = b[v] << 1;
    b[v] %= mod;
    tag[v]++;
    return;
  }
}
void modify2(long long l, long long r, long long v, long long l2,
             long long r2) {
  if (l == l2 && r == r2) {
    b[v]++;
    b[v] %= mod;
    return;
  }
  tag[v << 1] += tag[v];
  b[v << 1] *= tw[tag[v]];
  b[v << 1] %= mod;
  tag[v << 1 | 1] += tag[v];
  b[v << 1 | 1] *= tw[tag[v]];
  b[v << 1 | 1] %= mod;
  tag[v] = 0;
  long long mid = (l + r) >> 1;
  if (mid >= r2) {
    modify2(l, mid, v << 1, l2, r2);
  } else if (mid + 1 <= l2) {
    modify2(mid + 1, r, v << 1 | 1, l2, r2);
  } else {
    modify2(l, mid, v << 1, l2, mid);
    modify2(mid + 1, r, v << 1 | 1, mid + 1, r2);
  }
  b[v] = (b[v << 1] + b[v << 1 | 1]) % mod;
}
bool isp(long long x) {
  if (x == 1) {
    return 0;
  }
  for (long long i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  for (long long i = 1; i <= 100000; i++) {
    for (long long j = 1; j <= sqrt(i); j++) {
      if (i % j == 0) {
        divv[i].emplace_back(j);
        if (j != i / j) {
          divv[i].emplace_back(i / j);
        }
      }
    }
  }
  dif[1] = 1;
  for (long long i = 2; i <= 100000; i++) {
    dif[i] = i;
    for (long long j = 0; j < divv[i].size(); j++) {
      if (divv[i][j] != i) {
        dif[i] -= dif[divv[i][j]];
      }
    }
    dif[i] %= mod;
  }
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    v[a[i]].emplace_back(i);
  }
  ans = 0;
  for (long long i = 1; i <= 100000; i++) {
    cnt = 0;
    for (long long j = 1; i * j <= 100000; j++) {
      for (long long k = 0; k < v[i * j].size(); k++) {
        y = v[i * j][k];
        for (long long t = 0; t < divv[y].size(); t++) {
          if (!vis[divv[y][t]]) {
            b[cnt] = divv[y][t];
            cnt++;
            vis[divv[y][t]] = 1;
          }
          c[divv[y][t]]++;
        }
      }
    }
    x = 0;
    for (long long j = 0; j < cnt; j++) {
      x += (c[b[j]] * (c[b[j]] - 1) / 2 * dif[b[j]]);
      x %= mod;
    }
    for (long long j = 0; j < cnt; j++) {
      vis[b[j]] = 0;
      c[b[j]] = 0;
    }
    ans += (x)*dif[i];
    ans %= mod;
  }
  ans *= 2;
  for (long long i = 1; i <= n; i++) {
    ans += a[i] * i;
  }
  cout << (ans + mod) % mod;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 200010;
long long t, n, cnt, x, m, a[maxn], b[4 * maxn], tag[4 * maxn], ans, pos,
    c[maxn], l, r, mid, y, z, mx, k, mod = 1000000007, cnt1, cnt2, cnt3, cnt4,
                                     cnt5, cnt6, mn, vis[maxn], sum, pos1, pos2,
                                     dis[maxn];
long long dif[maxn];
long long tw[60], av, h;
double probability = 0;
set<long long> se;
vector<long long> v[maxn], gr[maxn], v1, v2, divv[maxn];
string s, s1, s2, s3, s4;
char cc[405][405], abc[205];
pair<long long, long long> p[maxn], pp;
map<long long, long long> mp;
char ch;
long long fpow(long long x, long long y) {
  if (y == 0) {
    return 1 % mod;
  }
  long long a = x % mod;
  long long a2 = 1 % mod;
  while (y > 1) {
    if (y % 2) {
      a2 *= a;
      a2 %= mod;
    }
    a *= a;
    a %= mod;
    y /= 2;
  }
  return (a * a2) % mod;
}
void build(long long l, long long r, long long v) {
  if (l == r) {
    b[v] = 0;
    return;
  }
  long long mid = (l + r) >> 1;
  build(l, mid, v << 1);
  build(mid + 1, r, v << 1 | 1);
  b[v] = 0;
}
long long qu(long long l, long long r, long long v, long long l2,
             long long r2) {
  if (l == l2 && r == r2) {
    return b[v];
  }
  tag[v << 1] += tag[v];
  b[v << 1] *= tw[tag[v]];
  b[v << 1] %= mod;
  tag[v << 1 | 1] += tag[v];
  b[v << 1 | 1] *= tw[tag[v]];
  b[v << 1 | 1] %= mod;
  tag[v] = 0;
  long long mid = (l + r) >> 1;
  if (mid >= r2) {
    return qu(l, mid, v << 1, l2, r2);
  } else if (mid + 1 <= l2) {
    return qu(mid + 1, r, v << 1 | 1, l2, r2);
  } else {
    return (qu(l, mid, v << 1, l2, mid) +
            qu(mid + 1, r, v << 1 | 1, mid + 1, r2)) %
           mod;
  }
}
void modify1(long long l, long long r, long long v, long long l2, long long r2,
             long long m) {
  if (l == l2 && r == r2) {
    b[v] = b[v] << 1;
    b[v] %= mod;
    tag[v]++;
    return;
  }
}
void modify2(long long l, long long r, long long v, long long l2,
             long long r2) {
  if (l == l2 && r == r2) {
    b[v]++;
    b[v] %= mod;
    return;
  }
  tag[v << 1] += tag[v];
  b[v << 1] *= tw[tag[v]];
  b[v << 1] %= mod;
  tag[v << 1 | 1] += tag[v];
  b[v << 1 | 1] *= tw[tag[v]];
  b[v << 1 | 1] %= mod;
  tag[v] = 0;
  long long mid = (l + r) >> 1;
  if (mid >= r2) {
    modify2(l, mid, v << 1, l2, r2);
  } else if (mid + 1 <= l2) {
    modify2(mid + 1, r, v << 1 | 1, l2, r2);
  } else {
    modify2(l, mid, v << 1, l2, mid);
    modify2(mid + 1, r, v << 1 | 1, mid + 1, r2);
  }
  b[v] = (b[v << 1] + b[v << 1 | 1]) % mod;
}
bool isp(long long x) {
  if (x == 1) {
    return 0;
  }
  for (long long i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  for (long long i = 1; i <= 100000; i++) {
    for (long long j = 1; j <= sqrt(i); j++) {
      if (i % j == 0) {
        divv[i].emplace_back(j);
        if (j != i / j) {
          divv[i].emplace_back(i / j);
        }
      }
    }
  }
  dif[1] = 1;
  for (long long i = 2; i <= 100000; i++) {
    dif[i] = i;
    for (long long j = 0; j < divv[i].size(); j++) {
      if (divv[i][j] != i) {
        dif[i] -= dif[divv[i][j]];
      }
    }
    dif[i] %= mod;
  }
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    v[a[i]].emplace_back(i);
  }
  ans = 0;
  for (long long i = 1; i <= 100000; i++) {
    cnt = 0;
    for (long long j = 1; i * j <= 100000; j++) {
      for (long long k = 0; k < v[i * j].size(); k++) {
        y = v[i * j][k];
        for (long long t = 0; t < divv[y].size(); t++) {
          if (!vis[divv[y][t]]) {
            b[cnt] = divv[y][t];
            cnt++;
            vis[divv[y][t]] = 1;
          }
          c[divv[y][t]]++;
        }
      }
    }
    x = 0;
    for (long long j = 0; j < cnt; j++) {
      x += (c[b[j]] * (c[b[j]] - 1) / 2 * dif[b[j]]);
      x %= mod;
    }
    for (long long j = 0; j < cnt; j++) {
      vis[b[j]] = 0;
      c[b[j]] = 0;
    }
    ans += (x)*dif[i];
    ans %= mod;
  }
  ans *= 2;
  for (long long i = 1; i <= n; i++) {
    ans += a[i] * i;
  }
  cout << (ans + mod) % mod;
}

```