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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;
#define fst first
#define snd second

using UINT = unsigned long long;
using ull = unsigned long long;
template <UINT MD>
struct ModInt {
  using M = ModInt;
  static constexpr UINT get_mod() { return MD; }
  const static M G;
  UINT v;
  ModInt(ll _v = 0) { set_v(UINT(_v % MD + MD)); }
  M &set_v(UINT _v) {
    v = (_v < MD) ? _v : _v - MD;
    return *this;
  }
  explicit operator bool() const { return v != 0; }
  M operator-() const { return M() - *this; }
  M operator+(const M &r) const { return M().set_v(v + r.v); }
  M operator-(const M &r) const { return M().set_v(v + MD - r.v); }
  M operator*(const M &r) const { return M().set_v(UINT(ull(v) * r.v % MD)); }
  M operator/(const M &r) const { return *this * r.inv(); }
  M &operator+=(const M &r) { return *this = *this + r; }
  M &operator-=(const M &r) { return *this = *this - r; }
  M &operator*=(const M &r) { return *this = *this * r; }
  M &operator/=(const M &r) { return *this = *this / r; }
  bool operator==(const M &r) const { return v == r.v; }
  M pow(ll n) const {
    M x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  M inv() const { return pow(MD - 2); }
  friend ostream &operator<<(ostream &os, const M &r) { return os << r.v; }
};
using Mint = ModInt<1000'000'007>;

const int N = 1e5 + 5;
int pr[N], phi[N];

void prec() {
  phi[1] = 1;
  for (int i = 2; i < N; i++) {
    if (pr[i] == 0) {
      phi[i] = i - 1;
      for (int j = i; j < N; j += i)
        pr[j] = i;
    } else {
      int x = i / pr[i];
      phi[i] = phi[x] * (pr[i] - (x % pr[i] != 0));
    }
  }
}

void factorize(int v, VI &facs) {
  for (int x = 1; x * x <= v; x++)
    if (v % x == 0) {
      facs.push_back(x);
      facs.push_back(v / x);
    }
  sort(facs.begin(), facs.end());
}

int a[N];
VI facs[N];

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    factorize(a[i], facs[i]);
  }
  Mint ans(0);
  for (int x = 1; x <= n; x++) {
    VI cfacs;
    for (int i = 1; i <= n / x; i++) {
      auto &f = facs[a[i * x]];
      cfacs.insert(cfacs.end(), f.begin(), f.end());
    }
    sort(cfacs.begin(), cfacs.end());
    cfacs.resize(unique(cfacs.begin(), cfacs.end()) - cfacs.begin());
    Mint term;
    for (int y : cfacs) {
      Mint cur;
      for (int i = 1; i <= n / x; i++)
        if (a[i * x] % y == 0) cur.v++;
      term += cur * cur * phi[y];
    }
    ans += term * phi[x];
  }
  cout << ans << '\n';
}

// #define TEST_CASES
// #define PRINT_CASE_NUMBERS

/*----- TEMPLATE ----------------------------------------------------------*/
int main(int argc, char *argv[]) {
#ifdef LOCAL_EXEC
  if (!(argc == 2 && string(argv[1]) == "-c")) {
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
  }
#else
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
#endif

  prec();

  int t = 1;
#ifdef TEST_CASES
  cin >> t;
#endif
  for (int it = 1; it <= t; it++) {
#ifdef PRINT_CASE_NUMBERS
    cout << "Case #" << it << ": ";
#endif
    solve();
  }

  return 0;
}
