#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, MAXN = 2e5 + 9, MAXX = 1e6 + 9, SQ = 447;
int n, q, cnt[MAXX], answer[MAXN], pre[MAXN], inv[MAXX], pr[MAXX];
vector<int> g[MAXN];
int power(int a, int b) {
  if (a < MAXX) return inv[a];
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD, b >>= 1;
  }
  return ret;
}
struct query {
  int l, r, ind, val;
  query(int _l = 0, int _r = 0, int _ind = 0, int _val = 0) {
    l = _l, r = _r, ind = _ind, val = _val;
  }
  bool operator<(const query &a) const {
    if (val == a.val) return r < a.r;
    return val < a.val;
  }
} qu[MAXN];
int main() {
  scanf("%d", &n);
  for (int i = 2; i < MAXX; i += 2) pr[i] = 2;
  for (int j = 3; j < MAXX; j += 2)
    if (!pr[j])
      for (int i = j; i < MAXX; i += j) pr[i] = j;
  pre[0] = 1;
  for (int i = 1, cur; i <= n; i++) {
    scanf("%d", &cur);
    pre[i] = 1ll * pre[i - 1] * cur % MOD;
    while (cur != 1) {
      int prm = pr[cur];
      g[i].push_back(prm);
      while (!(cur % prm)) cur /= prm;
    }
  }
  inv[1] = 1;
  for (int i = 2; i < MAXX; i++)
    inv[i] = MOD - (1ll * (MOD / i) * inv[MOD % i] % MOD);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%d%d", &qu[i].l, &qu[i].r), qu[i].val = qu[i].l / SQ, qu[i].ind = i;
  sort(qu + 1, qu + q + 1);
  for (int i = 1, b = 1, e = 0, cur = 1; i <= q; i++) {
    int l = qu[i].l, r = qu[i].r;
    while (e < r) {
      e++;
      for (int j = 0; j < g[e].size(); j++) {
        int &prm = g[e][j];
        if (!cnt[prm]) cur = 1ll * (prm - 1) * inv[prm] % MOD * cur % MOD;
        cnt[prm]++;
      }
    }
    while (e > r) {
      for (int j = 0; j < g[e].size(); j++) {
        int &prm = g[e][j];
        cnt[prm]--;
        if (!cnt[prm]) cur = 1ll * inv[prm - 1] * prm % MOD * cur % MOD;
      }
      e--;
    }
    while (b < l) {
      for (int j = 0; j < g[b].size(); j++) {
        int &prm = g[b][j];
        cnt[prm]--;
        if (!cnt[prm]) cur = 1ll * inv[prm - 1] * prm % MOD * cur % MOD;
      }
      b++;
    }
    while (b > l) {
      b--;
      for (int j = 0; j < g[b].size(); j++) {
        int &prm = g[b][j];
        if (!cnt[prm]) cur = 1ll * (prm - 1) * inv[prm] % MOD * cur % MOD;
        cnt[prm]++;
      }
    }
    answer[qu[i].ind] =
        1ll * pre[r] * power(pre[l - 1], MOD - 2) % MOD * cur % MOD;
  }
  for (int i = 1; i <= q; i++) printf("%d\n", answer[i]);
  return 0;
}

### Prompt

Your task is to create a Cpp solution 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 int MOD = 1e9 + 7, MAXN = 2e5 + 9, MAXX = 1e6 + 9, SQ = 447;
int n, q, cnt[MAXX], answer[MAXN], pre[MAXN], inv[MAXX], pr[MAXX];
vector<int> g[MAXN];
int power(int a, int b) {
  if (a < MAXX) return inv[a];
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD, b >>= 1;
  }
  return ret;
}
struct query {
  int l, r, ind, val;
  query(int _l = 0, int _r = 0, int _ind = 0, int _val = 0) {
    l = _l, r = _r, ind = _ind, val = _val;
  }
  bool operator<(const query &a) const {
    if (val == a.val) return r < a.r;
    return val < a.val;
  }
} qu[MAXN];
int main() {
  scanf("%d", &n);
  for (int i = 2; i < MAXX; i += 2) pr[i] = 2;
  for (int j = 3; j < MAXX; j += 2)
    if (!pr[j])
      for (int i = j; i < MAXX; i += j) pr[i] = j;
  pre[0] = 1;
  for (int i = 1, cur; i <= n; i++) {
    scanf("%d", &cur);
    pre[i] = 1ll * pre[i - 1] * cur % MOD;
    while (cur != 1) {
      int prm = pr[cur];
      g[i].push_back(prm);
      while (!(cur % prm)) cur /= prm;
    }
  }
  inv[1] = 1;
  for (int i = 2; i < MAXX; i++)
    inv[i] = MOD - (1ll * (MOD / i) * inv[MOD % i] % MOD);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%d%d", &qu[i].l, &qu[i].r), qu[i].val = qu[i].l / SQ, qu[i].ind = i;
  sort(qu + 1, qu + q + 1);
  for (int i = 1, b = 1, e = 0, cur = 1; i <= q; i++) {
    int l = qu[i].l, r = qu[i].r;
    while (e < r) {
      e++;
      for (int j = 0; j < g[e].size(); j++) {
        int &prm = g[e][j];
        if (!cnt[prm]) cur = 1ll * (prm - 1) * inv[prm] % MOD * cur % MOD;
        cnt[prm]++;
      }
    }
    while (e > r) {
      for (int j = 0; j < g[e].size(); j++) {
        int &prm = g[e][j];
        cnt[prm]--;
        if (!cnt[prm]) cur = 1ll * inv[prm - 1] * prm % MOD * cur % MOD;
      }
      e--;
    }
    while (b < l) {
      for (int j = 0; j < g[b].size(); j++) {
        int &prm = g[b][j];
        cnt[prm]--;
        if (!cnt[prm]) cur = 1ll * inv[prm - 1] * prm % MOD * cur % MOD;
      }
      b++;
    }
    while (b > l) {
      b--;
      for (int j = 0; j < g[b].size(); j++) {
        int &prm = g[b][j];
        if (!cnt[prm]) cur = 1ll * (prm - 1) * inv[prm] % MOD * cur % MOD;
        cnt[prm]++;
      }
    }
    answer[qu[i].ind] =
        1ll * pre[r] * power(pre[l - 1], MOD - 2) % MOD * cur % MOD;
  }
  for (int i = 1; i <= q; i++) printf("%d\n", answer[i]);
  return 0;
}

```