#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int N = 1e6 + 5;
const int NUM = 1e6 + 5;
const long long mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = buf;
int getc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
int read() {
  int x = 0;
  char ch = getc();
  while (!isdigit(ch)) ch = getc();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getc();
  return x;
}
void print(int x) {
  if (x > 9) print(x / 10);
  *O++ = x % 10 + '0';
}
long long qpow(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long mul[N], imul[N], a[N];
int n, q;
bool vis[NUM];
int pr[NUM], len, minp[NUM], mulp[NUM], inv[NUM];
long long val[NUM], ival[NUM];
void init(int n) {
  minp[1] = mulp[1] = inv[1] = 1;
  for (register int i = 2; i <= n; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  for (register int i = 2; i <= n; i++) {
    if (!vis[i]) {
      pr[len++] = i, minp[i] = mulp[i] = i;
      val[i] = 1ll * (i - 1) * inv[i] % mod;
      ival[i] = 1ll * i * inv[i - 1] % mod;
    }
    for (register int j = 0, v; j < len && pr[j] * i <= n; j++) {
      v = pr[j] * i, vis[v] = 1;
      if (i % pr[j] == 0) {
        minp[v] = pr[j];
        mulp[v] = mulp[i] * pr[j];
        break;
      }
      minp[v] = mulp[v] = pr[j];
    }
  }
}
long long c[N], ans[N];
void upd(int x, long long dlt) {
  while (x <= n) {
    c[x] = c[x] * dlt % mod;
    x += x & -x;
  }
}
long long qry(int x) {
  long long res = 1;
  while (x) {
    res = res * c[x] % mod;
    x ^= x & -x;
  }
  return res;
}
int lst[NUM], fir[N], nxt[N], L[N];
void update(int i, int p) {
  if (p <= 100) {
    lst[p] = i;
    return;
  }
  if (lst[p]) upd(lst[p], ival[p]);
  lst[p] = i, upd(i, val[p]);
}
int main() {
  O = obuf;
  init(1e6);
  n = read();
  mul[0] = imul[0] = 1ll;
  for (register int i = 1; i <= n; ++i) {
    a[i] = read(), c[i] = 1;
    mul[i] = mul[i - 1] * a[i] % mod;
  }
  imul[n] = qpow(mul[n], mod - 2);
  for (register int i = n - 1; i >= 1; --i)
    imul[i] = imul[i + 1] * a[i + 1] % mod;
  q = read();
  int l, r;
  for (register int i = 1; i <= q; ++i) {
    l = read(), r = read();
    if (l > r) swap(l, r);
    L[i] = l, nxt[i] = fir[r], fir[r] = i;
  }
  for (register int r = 1; r <= n; ++r) {
    int i = r;
    while (a[i] > 1) {
      update(i, minp[a[i]]);
      a[i] /= mulp[a[i]];
    }
    int l, id;
    for (register int _ = fir[r]; _; _ = nxt[_]) {
      l = L[_], id = _;
      ans[id] =
          qry(r) * qpow(qry(l - 1)) % mod * mul[r] % mod * imul[l - 1] % mod;
      for (register int k = 0; k < 25; ++k) {
        if (lst[pr[k]] >= l) ans[id] = ans[id] * val[pr[k]] % mod;
      }
    }
  }
  for (register int i = 1; i <= q; i++) print(ans[i]), *O++ = '\n';
  fwrite(obuf, O - obuf, 1, stdout);
  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>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int N = 1e6 + 5;
const int NUM = 1e6 + 5;
const long long mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = buf;
int getc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
int read() {
  int x = 0;
  char ch = getc();
  while (!isdigit(ch)) ch = getc();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getc();
  return x;
}
void print(int x) {
  if (x > 9) print(x / 10);
  *O++ = x % 10 + '0';
}
long long qpow(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long mul[N], imul[N], a[N];
int n, q;
bool vis[NUM];
int pr[NUM], len, minp[NUM], mulp[NUM], inv[NUM];
long long val[NUM], ival[NUM];
void init(int n) {
  minp[1] = mulp[1] = inv[1] = 1;
  for (register int i = 2; i <= n; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  for (register int i = 2; i <= n; i++) {
    if (!vis[i]) {
      pr[len++] = i, minp[i] = mulp[i] = i;
      val[i] = 1ll * (i - 1) * inv[i] % mod;
      ival[i] = 1ll * i * inv[i - 1] % mod;
    }
    for (register int j = 0, v; j < len && pr[j] * i <= n; j++) {
      v = pr[j] * i, vis[v] = 1;
      if (i % pr[j] == 0) {
        minp[v] = pr[j];
        mulp[v] = mulp[i] * pr[j];
        break;
      }
      minp[v] = mulp[v] = pr[j];
    }
  }
}
long long c[N], ans[N];
void upd(int x, long long dlt) {
  while (x <= n) {
    c[x] = c[x] * dlt % mod;
    x += x & -x;
  }
}
long long qry(int x) {
  long long res = 1;
  while (x) {
    res = res * c[x] % mod;
    x ^= x & -x;
  }
  return res;
}
int lst[NUM], fir[N], nxt[N], L[N];
void update(int i, int p) {
  if (p <= 100) {
    lst[p] = i;
    return;
  }
  if (lst[p]) upd(lst[p], ival[p]);
  lst[p] = i, upd(i, val[p]);
}
int main() {
  O = obuf;
  init(1e6);
  n = read();
  mul[0] = imul[0] = 1ll;
  for (register int i = 1; i <= n; ++i) {
    a[i] = read(), c[i] = 1;
    mul[i] = mul[i - 1] * a[i] % mod;
  }
  imul[n] = qpow(mul[n], mod - 2);
  for (register int i = n - 1; i >= 1; --i)
    imul[i] = imul[i + 1] * a[i + 1] % mod;
  q = read();
  int l, r;
  for (register int i = 1; i <= q; ++i) {
    l = read(), r = read();
    if (l > r) swap(l, r);
    L[i] = l, nxt[i] = fir[r], fir[r] = i;
  }
  for (register int r = 1; r <= n; ++r) {
    int i = r;
    while (a[i] > 1) {
      update(i, minp[a[i]]);
      a[i] /= mulp[a[i]];
    }
    int l, id;
    for (register int _ = fir[r]; _; _ = nxt[_]) {
      l = L[_], id = _;
      ans[id] =
          qry(r) * qpow(qry(l - 1)) % mod * mul[r] % mod * imul[l - 1] % mod;
      for (register int k = 0; k < 25; ++k) {
        if (lst[pr[k]] >= l) ans[id] = ans[id] * val[pr[k]] % mod;
      }
    }
  }
  for (register int i = 1; i <= q; i++) print(ans[i]), *O++ = '\n';
  fwrite(obuf, O - obuf, 1, stdout);
  return 0;
}

```