#include <bits/stdc++.h>
const int kMaxn = 2e5 + 10, kMaxa = 1e6 + 10, MOD = 1e9 + 7;
typedef int IntArr[kMaxn];
struct Query {
  int l, r, id;
  bool operator<(const Query& q) const { return r < q.r; }
} qry[kMaxn];
int n, q, totp, A[kMaxn], ans[kMaxn], prod[kMaxn], P[kMaxa], flag[kMaxa],
    minp[kMaxa], last[kMaxa];
namespace bit {
long long T[kMaxn];
void init() {
  for (int i = 1; i <= n; i++) T[i] = 1;
}
void Mult(int p, long long v) {
  for (; p <= n; p += p & -p) (T[p] *= v) %= MOD;
}
long long Query(int p) {
  long long ret = 1;
  for (; p > 0; p &= p - 1) (ret *= T[p]) %= MOD;
  return ret;
}
}  // namespace bit
namespace fast_io {
template <typename T>
void Read(T& x) {
  register char ch = getchar();
  x = 0;
  for (; !isdigit(ch); ch = getchar())
    ;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
}
}  // namespace fast_io
long long FastPow(long long bs, int ex = MOD - 2) {
  long long ret = 1;
  for (; ex; (bs *= bs) %= MOD, ex >>= 1)
    if (ex & 1) (ret *= bs) %= MOD;
  return ret;
}
int main() {
  using fast_io::Read;
  Read(n);
  int mxai = 0;
  for (int i = 1; i <= n; i++) {
    Read(A[i]);
    mxai = std::max(mxai, A[i]);
  }
  Read(q);
  for (int i = 0; i < q; i++) {
    Read(qry[i].l), Read(qry[i].r);
    qry[i].id = i;
  }
  for (int i = 2; i <= mxai; i++) {
    if (!flag[i]) P[totp++] = i, minp[i] = i;
    for (int j = 0, pd; j < totp && (pd = i * P[j]) <= mxai; j++) {
      flag[pd] = 1, minp[pd] = P[j];
      if (i % P[j] == 0) break;
    }
  }
  prod[0] = 1;
  for (int i = 1; i <= n; i++) prod[i] = (long long)prod[i - 1] * A[i] % MOD;
  bit::init();
  std::sort(qry, qry + q);
  int cur = 0;
  for (int i = 0; i < q; i++) {
    for (; cur < qry[i].r;) {
      for (int t = A[++cur], p; t > 1;) {
        if (last[p = minp[t]]) {
          bit::Mult(last[p], FastPow(p - 1));
          bit::Mult(last[p], p);
        }
        bit::Mult(cur, p - 1);
        bit::Mult(cur, FastPow(p));
        last[p] = cur, t /= p;
      }
    }
    ans[qry[i].id] =
        bit::Query(qry[i].r) * prod[qry[i].r] % MOD *
        FastPow(bit::Query(qry[i].l - 1) * prod[qry[i].l - 1] % MOD) % MOD;
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[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>
const int kMaxn = 2e5 + 10, kMaxa = 1e6 + 10, MOD = 1e9 + 7;
typedef int IntArr[kMaxn];
struct Query {
  int l, r, id;
  bool operator<(const Query& q) const { return r < q.r; }
} qry[kMaxn];
int n, q, totp, A[kMaxn], ans[kMaxn], prod[kMaxn], P[kMaxa], flag[kMaxa],
    minp[kMaxa], last[kMaxa];
namespace bit {
long long T[kMaxn];
void init() {
  for (int i = 1; i <= n; i++) T[i] = 1;
}
void Mult(int p, long long v) {
  for (; p <= n; p += p & -p) (T[p] *= v) %= MOD;
}
long long Query(int p) {
  long long ret = 1;
  for (; p > 0; p &= p - 1) (ret *= T[p]) %= MOD;
  return ret;
}
}  // namespace bit
namespace fast_io {
template <typename T>
void Read(T& x) {
  register char ch = getchar();
  x = 0;
  for (; !isdigit(ch); ch = getchar())
    ;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
}
}  // namespace fast_io
long long FastPow(long long bs, int ex = MOD - 2) {
  long long ret = 1;
  for (; ex; (bs *= bs) %= MOD, ex >>= 1)
    if (ex & 1) (ret *= bs) %= MOD;
  return ret;
}
int main() {
  using fast_io::Read;
  Read(n);
  int mxai = 0;
  for (int i = 1; i <= n; i++) {
    Read(A[i]);
    mxai = std::max(mxai, A[i]);
  }
  Read(q);
  for (int i = 0; i < q; i++) {
    Read(qry[i].l), Read(qry[i].r);
    qry[i].id = i;
  }
  for (int i = 2; i <= mxai; i++) {
    if (!flag[i]) P[totp++] = i, minp[i] = i;
    for (int j = 0, pd; j < totp && (pd = i * P[j]) <= mxai; j++) {
      flag[pd] = 1, minp[pd] = P[j];
      if (i % P[j] == 0) break;
    }
  }
  prod[0] = 1;
  for (int i = 1; i <= n; i++) prod[i] = (long long)prod[i - 1] * A[i] % MOD;
  bit::init();
  std::sort(qry, qry + q);
  int cur = 0;
  for (int i = 0; i < q; i++) {
    for (; cur < qry[i].r;) {
      for (int t = A[++cur], p; t > 1;) {
        if (last[p = minp[t]]) {
          bit::Mult(last[p], FastPow(p - 1));
          bit::Mult(last[p], p);
        }
        bit::Mult(cur, p - 1);
        bit::Mult(cur, FastPow(p));
        last[p] = cur, t /= p;
      }
    }
    ans[qry[i].id] =
        bit::Query(qry[i].r) * prod[qry[i].r] % MOD *
        FastPow(bit::Query(qry[i].l - 1) * prod[qry[i].l - 1] % MOD) % MOD;
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
  return 0;
}

```