#include <bits/stdc++.h>
using namespace std;
const int nmax = 200005;
const long long mod = 1000 * 1000 * 1000 + 7;
vector<long long> d[5 * nmax];
vector<pair<int, int> > q[nmax];
long long part[nmax], a[nmax], ans[nmax], aib[nmax];
int lst[5 * nmax];
int n, i, j, Q, l, r, x, poz;
long long expo(long long A, int B) {
  long long ret = 1, p2 = A;
  for (int p = 0; p <= 30; p++) {
    if (((1 << p) & B)) ret = (1LL * ret * p2) % mod;
    p2 = (1LL * p2 * p2) % mod;
  }
  return ret;
}
inline int lbit(int x) { return (((x ^ (x - 1))) & x); }
void update(int poz, long long val) {
  for (int idx = poz; idx <= n; idx += lbit(idx))
    aib[idx] = (1LL * aib[idx] * val) % mod;
}
long long compute(int poz) {
  long long ret = 1;
  for (int idx = poz; idx > 0; idx -= lbit(idx))
    ret = (1LL * ret * aib[idx]) % mod;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  part[0] = 1;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    part[i] = (1LL * part[i - 1] * a[i]) % mod;
  }
  cin >> Q;
  for (i = 1; i <= Q; i++) {
    cin >> l >> r;
    q[r].push_back({l, i});
    ans[i] = (1LL * expo(part[l - 1], mod - 2) * part[r]) % mod;
  }
  int vmax = 1000 * 1000;
  for (i = 2; i <= vmax; i++)
    if (!d[i].size())
      for (j = i; j <= vmax; j += i) d[j].push_back(i);
  for (i = 1; i <= n; i++) aib[i] = 1;
  long long fv;
  for (i = 1; i <= n; i++) {
    x = a[i];
    for (j = 0; j < d[x].size(); j++) {
      poz = lst[d[x][j]];
      if (poz) update(poz, (1LL * d[x][j] * expo(d[x][j] - 1, mod - 2)) % mod);
      update(i, (1LL * (d[x][j] - 1) * expo(d[x][j], mod - 2)) % mod);
      lst[d[x][j]] = i;
    }
    for (j = 0; j < q[i].size(); j++) {
      fv = (1LL * compute(i) * expo(compute(q[i][j].first - 1), mod - 2)) % mod;
      ans[q[i][j].second] = (1LL * ans[q[i][j].second] * fv) % mod;
    }
  }
  for (i = 1; i <= Q; i++) cout << ans[i] << '\n';
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Today on a math lesson the teacher told Vovochka that the Euler function of a positive integer φ(n) is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. The number 1 is coprime to all the positive integers and φ(1) = 1.

Now the teacher gave Vovochka an array of n positive integers a1, a2, ..., an and a task to process q queries li ri — to calculate and print <image> modulo 109 + 7. As it is too hard for a second grade school student, you've decided to help Vovochka.

Input

The first line of the input contains number n (1 ≤ n ≤ 200 000) — the length of the array given to Vovochka. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106).

The third line contains integer q (1 ≤ q ≤ 200 000) — the number of queries. Next q lines contain the queries, one per line. Each query is defined by the boundaries of the segment li and ri (1 ≤ li ≤ ri ≤ n).

Output

Print q numbers — the value of the Euler function for each query, calculated modulo 109 + 7.

Examples

Input

10
1 2 3 4 5 6 7 8 9 10
7
1 1
3 8
5 6
4 8
8 10
7 9
7 10


Output

1
4608
8
1536
192
144
1152


Input

7
24 63 13 52 6 10 1
6
3 5
4 7
1 7
2 4
3 6
2 6


Output

1248
768
12939264
11232
9984
539136

Note

In the second sample the values are calculated like that:

  * φ(13·52·6) = φ(4056) = 1248
  * φ(52·6·10·1) = φ(3120) = 768
  * φ(24·63·13·52·6·10·1) = φ(61326720) = 12939264
  * φ(63·13·52) = φ(42588) = 11232
  * φ(13·52·6·10) = φ(40560) = 9984
  * φ(63·13·52·6·10) = φ(2555280) = 539136

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int nmax = 200005;
const long long mod = 1000 * 1000 * 1000 + 7;
vector<long long> d[5 * nmax];
vector<pair<int, int> > q[nmax];
long long part[nmax], a[nmax], ans[nmax], aib[nmax];
int lst[5 * nmax];
int n, i, j, Q, l, r, x, poz;
long long expo(long long A, int B) {
  long long ret = 1, p2 = A;
  for (int p = 0; p <= 30; p++) {
    if (((1 << p) & B)) ret = (1LL * ret * p2) % mod;
    p2 = (1LL * p2 * p2) % mod;
  }
  return ret;
}
inline int lbit(int x) { return (((x ^ (x - 1))) & x); }
void update(int poz, long long val) {
  for (int idx = poz; idx <= n; idx += lbit(idx))
    aib[idx] = (1LL * aib[idx] * val) % mod;
}
long long compute(int poz) {
  long long ret = 1;
  for (int idx = poz; idx > 0; idx -= lbit(idx))
    ret = (1LL * ret * aib[idx]) % mod;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  part[0] = 1;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    part[i] = (1LL * part[i - 1] * a[i]) % mod;
  }
  cin >> Q;
  for (i = 1; i <= Q; i++) {
    cin >> l >> r;
    q[r].push_back({l, i});
    ans[i] = (1LL * expo(part[l - 1], mod - 2) * part[r]) % mod;
  }
  int vmax = 1000 * 1000;
  for (i = 2; i <= vmax; i++)
    if (!d[i].size())
      for (j = i; j <= vmax; j += i) d[j].push_back(i);
  for (i = 1; i <= n; i++) aib[i] = 1;
  long long fv;
  for (i = 1; i <= n; i++) {
    x = a[i];
    for (j = 0; j < d[x].size(); j++) {
      poz = lst[d[x][j]];
      if (poz) update(poz, (1LL * d[x][j] * expo(d[x][j] - 1, mod - 2)) % mod);
      update(i, (1LL * (d[x][j] - 1) * expo(d[x][j], mod - 2)) % mod);
      lst[d[x][j]] = i;
    }
    for (j = 0; j < q[i].size(); j++) {
      fv = (1LL * compute(i) * expo(compute(q[i][j].first - 1), mod - 2)) % mod;
      ans[q[i][j].second] = (1LL * ans[q[i][j].second] * fv) % mod;
    }
  }
  for (i = 1; i <= Q; i++) cout << ans[i] << '\n';
  return 0;
}

```