#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * 1e5 + 10;
namespace INPUT_SPACE {
const int BS = (1 << 24) + 5;
char Buffer[BS], *HD, *TL;
char gc() {
  if (HD == TL) TL = (HD = Buffer) + fread(Buffer, 1, BS, stdin);
  return (HD == TL) ? EOF : *HD++;
}
inline int inn() {
  int x, ch, sgn = 1;
  while (((ch = gc()) < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-')
    sgn = -1, x = 0;
  else
    x = ch ^ '0';
  while ((ch = gc()) >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ '0');
  return x * sgn;
}
}  // namespace INPUT_SPACE
using INPUT_SPACE::inn;
const unsigned long long mod = 1e9 + 7;
const int B = 570;
inline unsigned long long po(unsigned long long a, unsigned long long p) {
  unsigned long long r = 1;
  for (; p; p >>= 1, a = a * a % mod)
    if (p & 1) r = r * a % mod;
  return r;
}
int zhi[N];
int ct;
int ct2;
int id[N];
bool book[N];
unsigned long long xs[N];
unsigned long long xs2[N];
unsigned long long inv[N];
unsigned long long ixs[N];
int mi[N];
unsigned long long ans[N];
int n;
int m;
inline void pre() {
  mi[1] = 1;
  for (int i = 2; i < N; i++) {
    if (book[i] == false) {
      zhi[++ct] = i;
      mi[i] = i;
    }
    for (int j = 1; j <= ct && i * zhi[j] < N; j++) {
      int ke = i * zhi[j];
      book[ke] = true;
      if (i % zhi[j] == 0) {
        mi[ke] = mi[i];
        break;
      } else
        mi[ke] = zhi[j];
    }
  }
  inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  for (int i = 2; i < N; i++)
    if (book[i] == false)
      xs[i] = (i - 1) * inv[i] % mod, ixs[i] = inv[i - 1] * i % mod;
  for (int i = 1; i <= ct; i++)
    if (zhi[i] <= 1000) id[zhi[i]] = i, xs2[i] = xs[zhi[i]], ct2++;
}
int b[N];
int bdv[N];
unsigned long long mul = 1;
int cnt[N];
int tim[M][200];
inline void ins(int pos) {
  (mul *= b[pos]) %= mod;
  int nw = bdv[pos];
  if (nw) {
    ++cnt[nw];
    if (cnt[nw] == 1) (mul *= xs[nw]) %= mod;
  }
}
inline void del(int pos) {
  (mul *= inv[b[pos]]) %= mod;
  int nw = bdv[pos];
  if (nw) {
    --cnt[nw];
    if (cnt[nw] == 0) (mul *= ixs[nw]) %= mod;
  }
}
inline unsigned long long calc(int l, int r) {
  unsigned long long res = mul;
  int* p = tim[r];
  for (int i = 1; i <= ct2; i++)
    if (p[i] >= l) (res *= xs2[i]) %= mod;
  return res;
}
struct qry {
  int l;
  int r;
  int id;
} qr[N];
int tr[N];
int hd;
inline bool cmp1(const qry& a, const qry& b) { return a.r < b.r; }
inline bool cmp2(const qry& a, const qry& b) { return a.l < b.l; }
inline bool cmp3(const qry& a, const qry& b) { return a.r > b.r; }
int main() {
  pre();
  n = inn();
  for (int i = 1; i <= n; i++) b[i] = inn();
  m = inn();
  for (int i = 1; i <= m; i++) qr[i].l = inn(), qr[i].r = inn(), qr[i].id = i;
  for (int i = 1; i <= ct2; i++) tim[0][i] = -1;
  for (int i = 1; i <= n; i++) {
    int nu = b[i];
    hd = 0;
    while (nu != 1) {
      int p = mi[nu];
      tr[++hd] = p;
      while (nu % p == 0) nu /= p;
    }
    for (int k = 1; k <= ct2; k++) tim[i][k] = tim[i - 1][k];
    for (int k = 1; k <= hd; k++)
      if (tr[k] > 1000)
        bdv[i] = tr[k];
      else
        tim[i][id[tr[k]]] = i;
  }
  sort(qr + 1, qr + m + 1, cmp2);
  for (int j = 1, tp = 1; j <= m; j += B, tp ^= 1)
    if (tp)
      sort(qr + j, qr + min(j + B, m + 1), cmp1);
    else
      sort(qr + j, qr + min(j + B, m + 1), cmp3);
  int dl = 0;
  int dr = -1;
  for (int i = 1; i <= m; i++) {
    if (dr < qr[i].l || dl > qr[i].r) {
      for (int k = dl; k <= dr; k++) del(k);
      for (int k = qr[i].l; k <= qr[i].r; k++) ins(k);
      dl = qr[i].l;
      dr = qr[i].r;
    } else {
      while (dl < qr[i].l) del(dl++);
      while (dl > qr[i].l) ins(--dl);
      while (dr < qr[i].r) ins(++dr);
      while (dr > qr[i].r) del(dr--);
    }
    ans[qr[i].id] = calc(qr[i].l, qr[i].r);
  }
  for (int i = 1; i <= m; i++) printf("%I64d\n", ans[i]);
  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>
#pragma GCC optimize(2)
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * 1e5 + 10;
namespace INPUT_SPACE {
const int BS = (1 << 24) + 5;
char Buffer[BS], *HD, *TL;
char gc() {
  if (HD == TL) TL = (HD = Buffer) + fread(Buffer, 1, BS, stdin);
  return (HD == TL) ? EOF : *HD++;
}
inline int inn() {
  int x, ch, sgn = 1;
  while (((ch = gc()) < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-')
    sgn = -1, x = 0;
  else
    x = ch ^ '0';
  while ((ch = gc()) >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ '0');
  return x * sgn;
}
}  // namespace INPUT_SPACE
using INPUT_SPACE::inn;
const unsigned long long mod = 1e9 + 7;
const int B = 570;
inline unsigned long long po(unsigned long long a, unsigned long long p) {
  unsigned long long r = 1;
  for (; p; p >>= 1, a = a * a % mod)
    if (p & 1) r = r * a % mod;
  return r;
}
int zhi[N];
int ct;
int ct2;
int id[N];
bool book[N];
unsigned long long xs[N];
unsigned long long xs2[N];
unsigned long long inv[N];
unsigned long long ixs[N];
int mi[N];
unsigned long long ans[N];
int n;
int m;
inline void pre() {
  mi[1] = 1;
  for (int i = 2; i < N; i++) {
    if (book[i] == false) {
      zhi[++ct] = i;
      mi[i] = i;
    }
    for (int j = 1; j <= ct && i * zhi[j] < N; j++) {
      int ke = i * zhi[j];
      book[ke] = true;
      if (i % zhi[j] == 0) {
        mi[ke] = mi[i];
        break;
      } else
        mi[ke] = zhi[j];
    }
  }
  inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  for (int i = 2; i < N; i++)
    if (book[i] == false)
      xs[i] = (i - 1) * inv[i] % mod, ixs[i] = inv[i - 1] * i % mod;
  for (int i = 1; i <= ct; i++)
    if (zhi[i] <= 1000) id[zhi[i]] = i, xs2[i] = xs[zhi[i]], ct2++;
}
int b[N];
int bdv[N];
unsigned long long mul = 1;
int cnt[N];
int tim[M][200];
inline void ins(int pos) {
  (mul *= b[pos]) %= mod;
  int nw = bdv[pos];
  if (nw) {
    ++cnt[nw];
    if (cnt[nw] == 1) (mul *= xs[nw]) %= mod;
  }
}
inline void del(int pos) {
  (mul *= inv[b[pos]]) %= mod;
  int nw = bdv[pos];
  if (nw) {
    --cnt[nw];
    if (cnt[nw] == 0) (mul *= ixs[nw]) %= mod;
  }
}
inline unsigned long long calc(int l, int r) {
  unsigned long long res = mul;
  int* p = tim[r];
  for (int i = 1; i <= ct2; i++)
    if (p[i] >= l) (res *= xs2[i]) %= mod;
  return res;
}
struct qry {
  int l;
  int r;
  int id;
} qr[N];
int tr[N];
int hd;
inline bool cmp1(const qry& a, const qry& b) { return a.r < b.r; }
inline bool cmp2(const qry& a, const qry& b) { return a.l < b.l; }
inline bool cmp3(const qry& a, const qry& b) { return a.r > b.r; }
int main() {
  pre();
  n = inn();
  for (int i = 1; i <= n; i++) b[i] = inn();
  m = inn();
  for (int i = 1; i <= m; i++) qr[i].l = inn(), qr[i].r = inn(), qr[i].id = i;
  for (int i = 1; i <= ct2; i++) tim[0][i] = -1;
  for (int i = 1; i <= n; i++) {
    int nu = b[i];
    hd = 0;
    while (nu != 1) {
      int p = mi[nu];
      tr[++hd] = p;
      while (nu % p == 0) nu /= p;
    }
    for (int k = 1; k <= ct2; k++) tim[i][k] = tim[i - 1][k];
    for (int k = 1; k <= hd; k++)
      if (tr[k] > 1000)
        bdv[i] = tr[k];
      else
        tim[i][id[tr[k]]] = i;
  }
  sort(qr + 1, qr + m + 1, cmp2);
  for (int j = 1, tp = 1; j <= m; j += B, tp ^= 1)
    if (tp)
      sort(qr + j, qr + min(j + B, m + 1), cmp1);
    else
      sort(qr + j, qr + min(j + B, m + 1), cmp3);
  int dl = 0;
  int dr = -1;
  for (int i = 1; i <= m; i++) {
    if (dr < qr[i].l || dl > qr[i].r) {
      for (int k = dl; k <= dr; k++) del(k);
      for (int k = qr[i].l; k <= qr[i].r; k++) ins(k);
      dl = qr[i].l;
      dr = qr[i].r;
    } else {
      while (dl < qr[i].l) del(dl++);
      while (dl > qr[i].l) ins(--dl);
      while (dr < qr[i].r) ins(++dr);
      while (dr > qr[i].r) del(dr--);
    }
    ans[qr[i].id] = calc(qr[i].l, qr[i].r);
  }
  for (int i = 1; i <= m; i++) printf("%I64d\n", ans[i]);
  return 0;
}

```