#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, a[200001], pre[200001];
int p[1000001], ST[800000];
int primeID[1000000];
queue<int> pi[79000];
int q, l[200001], r[200001], id[200001];
int ans[200001];
void eratosthenes_sieve() {
  int cnt = 0;
  for (int i = 2; i <= 1e6; ++i)
    if (!p[i]) {
      primeID[i] = cnt++;
      for (int j = 1; i * j <= 1e6; ++j) p[i * j] = i;
    }
}
int power(int a, int b) {
  if (b == 0) return 1;
  int res = power(a, b >> 1);
  res = 1ll * res * res % MOD;
  if (b & 1) res = 1ll * res * a % MOD;
  return res;
}
bool cmp(int i, int j) { return l[i] < l[j]; }
void updateST(int k, int l, int r, int x, int v) {
  if (l > x || x > r)
    return;
  else if (l == r)
    ST[k] = 1ll * ST[k] * v % MOD;
  else
    updateST(2 * k, l, (l + r) / 2, x, v),
        updateST(2 * k + 1, (l + r) / 2 + 1, r, x, v),
        ST[k] = 1ll * ST[2 * k] * ST[2 * k + 1] % MOD;
}
int queryST(int k, int l, int r, int x, int y) {
  if (l > y || x > r)
    return 1;
  else if (x <= l && r <= y)
    return ST[k];
  else {
    int ans1 = queryST(2 * k, l, (l + r) / 2, x, y);
    int ans2 = queryST(2 * k + 1, (l + r) / 2 + 1, r, x, y);
    return 1ll * ans1 * ans2 % MOD;
  }
}
int main() {
  eratosthenes_sieve();
  cin >> n;
  for (int i = 1; i <= 4 * n; ++i) ST[i] = 1;
  pre[0] = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pre[i] = 1ll * pre[i - 1] * a[i] % MOD;
    for (int x = a[i]; x > 1;) {
      int d = p[x];
      pi[primeID[d]].push(i);
      if (pi[primeID[d]].size() == 1)
        updateST(1, 1, n, i, 1ll * (d - 1) * power(d, MOD - 2) % MOD);
      while (x % d == 0) x /= d;
    }
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) cin >> l[i] >> r[i], id[i] = i;
  sort(id + 1, id + q + 1, cmp);
  for (int i = 1, j = 1; i <= q; ++i) {
    for (; j < l[id[i]]; ++j)
      for (int x = a[j]; x > 1;) {
        int d = p[x];
        pi[primeID[d]].pop();
        updateST(1, 1, n, pi[primeID[d]].front(),
                 1ll * (d - 1) * power(d, MOD - 2) % MOD);
        while (x % d == 0) x /= d;
      }
    ans[id[i]] = (1ll * pre[r[id[i]]] * power(pre[j - 1], MOD - 2) % MOD) *
                 queryST(1, 1, n, j, r[id[i]]) % MOD;
  }
  for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

### Prompt

In cpp, your task is to solve 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 int MOD = 1e9 + 7;
int n, a[200001], pre[200001];
int p[1000001], ST[800000];
int primeID[1000000];
queue<int> pi[79000];
int q, l[200001], r[200001], id[200001];
int ans[200001];
void eratosthenes_sieve() {
  int cnt = 0;
  for (int i = 2; i <= 1e6; ++i)
    if (!p[i]) {
      primeID[i] = cnt++;
      for (int j = 1; i * j <= 1e6; ++j) p[i * j] = i;
    }
}
int power(int a, int b) {
  if (b == 0) return 1;
  int res = power(a, b >> 1);
  res = 1ll * res * res % MOD;
  if (b & 1) res = 1ll * res * a % MOD;
  return res;
}
bool cmp(int i, int j) { return l[i] < l[j]; }
void updateST(int k, int l, int r, int x, int v) {
  if (l > x || x > r)
    return;
  else if (l == r)
    ST[k] = 1ll * ST[k] * v % MOD;
  else
    updateST(2 * k, l, (l + r) / 2, x, v),
        updateST(2 * k + 1, (l + r) / 2 + 1, r, x, v),
        ST[k] = 1ll * ST[2 * k] * ST[2 * k + 1] % MOD;
}
int queryST(int k, int l, int r, int x, int y) {
  if (l > y || x > r)
    return 1;
  else if (x <= l && r <= y)
    return ST[k];
  else {
    int ans1 = queryST(2 * k, l, (l + r) / 2, x, y);
    int ans2 = queryST(2 * k + 1, (l + r) / 2 + 1, r, x, y);
    return 1ll * ans1 * ans2 % MOD;
  }
}
int main() {
  eratosthenes_sieve();
  cin >> n;
  for (int i = 1; i <= 4 * n; ++i) ST[i] = 1;
  pre[0] = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pre[i] = 1ll * pre[i - 1] * a[i] % MOD;
    for (int x = a[i]; x > 1;) {
      int d = p[x];
      pi[primeID[d]].push(i);
      if (pi[primeID[d]].size() == 1)
        updateST(1, 1, n, i, 1ll * (d - 1) * power(d, MOD - 2) % MOD);
      while (x % d == 0) x /= d;
    }
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) cin >> l[i] >> r[i], id[i] = i;
  sort(id + 1, id + q + 1, cmp);
  for (int i = 1, j = 1; i <= q; ++i) {
    for (; j < l[id[i]]; ++j)
      for (int x = a[j]; x > 1;) {
        int d = p[x];
        pi[primeID[d]].pop();
        updateST(1, 1, n, pi[primeID[d]].front(),
                 1ll * (d - 1) * power(d, MOD - 2) % MOD);
        while (x % d == 0) x /= d;
      }
    ans[id[i]] = (1ll * pre[r[id[i]]] * power(pre[j - 1], MOD - 2) % MOD) *
                 queryST(1, 1, n, j, r[id[i]]) % MOD;
  }
  for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

```