#include <bits/stdc++.h>
using namespace std;
const long long int maxn = (1e6) + 10, mod = 1e9 + 7;
long long int n, a[maxn], res[maxn], m, pnt[maxn], par[maxn], seg[4 * maxn],
    ans[maxn];
vector<pair<long long int, long long int> > r[maxn];
vector<long long int> v[maxn];
bool mark[maxn];
long long int pw(long long int a, long long int b) {
  if (b == 0) return 1;
  long long int res = pw(a, b >> 1) % mod;
  res *= res;
  res %= mod;
  if (b % 2) res *= a;
  return res % mod;
}
void build(long long int s = 0, long long int e = n, long long int id = 1) {
  seg[id] = 1;
  if (s == e - 1) return;
  long long int mid = (s + e) >> 1;
  build(s, mid, 2 * id);
  build(mid, e, 2 * id + 1);
}
void zar(long long int l, long long int r, long long int x, long long int s = 0,
         long long int e = n, long long int id = 1) {
  if (r <= s || e <= l) return;
  if (l <= s && e <= r) {
    seg[id] *= x;
    seg[id] %= mod;
    return;
  }
  long long int mid = (s + e) >> 1;
  zar(l, r, x, s, mid, 2 * id);
  zar(l, r, x, mid, e, 2 * id + 1);
}
long long int get(long long int cur, long long int s = 0, long long int e = n,
                  long long int id = 1) {
  if (s == e - 1) return seg[id];
  long long int mid = (s + e) >> 1;
  if (cur < mid)
    return (seg[id] * get(cur, s, mid, 2 * id)) % mod;
  else
    return (seg[id] * get(cur, mid, e, 2 * id + 1)) % mod;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (long long int i = 1; i <= n; i++) cin >> a[i];
  cin >> m;
  par[0] = 1;
  for (long long int i = 1; i <= n; i++) {
    par[i] = (par[i - 1] * a[i]) % mod;
  }
  for (long long int i = 0; i < m; i++) {
    long long int x, y;
    cin >> x >> y;
    r[y].push_back({x, i});
  }
  for (long long int i = 2; i <= 1000000; i++) {
    if (!mark[i]) {
      for (long long int j = 1; j * i <= 1000000; j++) {
        v[i * j].push_back(i);
        mark[i * j] = 1;
      }
    }
  }
  memset(pnt, -1, sizeof pnt);
  build();
  for (long long int i = 1; i <= n; i++) {
    for (long long int j = 0; j < v[a[i]].size(); j++) {
      zar(pnt[v[a[i]][j]] + 1, i,
          ((v[a[i]][j] - 1) * pw(v[a[i]][j], mod - 2)) % mod);
      pnt[v[a[i]][j]] = i - 1;
    }
    for (long long int j = 0; j < r[i].size(); j++)
      ans[r[i][j].second] =
          (((par[i] * pw(par[r[i][j].first - 1], mod - 2)) % mod) *
           get(r[i][j].first - 1)) %
          mod;
  }
  for (long long int i = 0; i < m; i++) cout << ans[i] % mod << ' ';
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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 long long int maxn = (1e6) + 10, mod = 1e9 + 7;
long long int n, a[maxn], res[maxn], m, pnt[maxn], par[maxn], seg[4 * maxn],
    ans[maxn];
vector<pair<long long int, long long int> > r[maxn];
vector<long long int> v[maxn];
bool mark[maxn];
long long int pw(long long int a, long long int b) {
  if (b == 0) return 1;
  long long int res = pw(a, b >> 1) % mod;
  res *= res;
  res %= mod;
  if (b % 2) res *= a;
  return res % mod;
}
void build(long long int s = 0, long long int e = n, long long int id = 1) {
  seg[id] = 1;
  if (s == e - 1) return;
  long long int mid = (s + e) >> 1;
  build(s, mid, 2 * id);
  build(mid, e, 2 * id + 1);
}
void zar(long long int l, long long int r, long long int x, long long int s = 0,
         long long int e = n, long long int id = 1) {
  if (r <= s || e <= l) return;
  if (l <= s && e <= r) {
    seg[id] *= x;
    seg[id] %= mod;
    return;
  }
  long long int mid = (s + e) >> 1;
  zar(l, r, x, s, mid, 2 * id);
  zar(l, r, x, mid, e, 2 * id + 1);
}
long long int get(long long int cur, long long int s = 0, long long int e = n,
                  long long int id = 1) {
  if (s == e - 1) return seg[id];
  long long int mid = (s + e) >> 1;
  if (cur < mid)
    return (seg[id] * get(cur, s, mid, 2 * id)) % mod;
  else
    return (seg[id] * get(cur, mid, e, 2 * id + 1)) % mod;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (long long int i = 1; i <= n; i++) cin >> a[i];
  cin >> m;
  par[0] = 1;
  for (long long int i = 1; i <= n; i++) {
    par[i] = (par[i - 1] * a[i]) % mod;
  }
  for (long long int i = 0; i < m; i++) {
    long long int x, y;
    cin >> x >> y;
    r[y].push_back({x, i});
  }
  for (long long int i = 2; i <= 1000000; i++) {
    if (!mark[i]) {
      for (long long int j = 1; j * i <= 1000000; j++) {
        v[i * j].push_back(i);
        mark[i * j] = 1;
      }
    }
  }
  memset(pnt, -1, sizeof pnt);
  build();
  for (long long int i = 1; i <= n; i++) {
    for (long long int j = 0; j < v[a[i]].size(); j++) {
      zar(pnt[v[a[i]][j]] + 1, i,
          ((v[a[i]][j] - 1) * pw(v[a[i]][j], mod - 2)) % mod);
      pnt[v[a[i]][j]] = i - 1;
    }
    for (long long int j = 0; j < r[i].size(); j++)
      ans[r[i][j].second] =
          (((par[i] * pw(par[r[i][j].first - 1], mod - 2)) % mod) *
           get(r[i][j].first - 1)) %
          mod;
  }
  for (long long int i = 0; i < m; i++) cout << ans[i] % mod << ' ';
  return 0;
}

```