#include <bits/stdc++.h>
using namespace std;
map<int, int> pre;
const long long mod = 1e9 + 7;
long long n, m, sum[200005], arr[200005], ans[200005], a[200005 << 2];
long long prime[205] = {
    0,   2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
    47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,  101, 103, 107, 109,
    113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
    197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
    281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373,
    379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
    463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
    571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
    659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
    761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
    863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
    977, 983, 991, 997};
long long pcnt = 168;
long long qpow(long long a, long long b) {
  long long ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) ret = ret * a % mod;
    a = a * a % mod;
  }
  return ret;
}
struct Query {
  int l, r, idx;
} q[200005];
bool cmp(const Query& a, const Query& b) { return a.r < b.r; }
void push_up(int p) { a[p] = a[(p << 1)] * a[(p << 1 | 1)] % mod; }
void update(int pos, int l, int r, int p, long long k) {
  if (l == r) {
    a[p] = a[p] * k % mod;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(pos, l, mid, (p << 1), k);
  else
    update(pos, mid + 1, r, (p << 1 | 1), k);
  push_up(p);
}
long long query(long long nl, long long nr, long long l, long long r,
                long long p) {
  if (nl <= l && r <= nr) return a[p];
  int mid = (l + r) >> 1;
  long long ret = 1;
  if (nl <= mid) ret = query(nl, nr, l, mid, (p << 1));
  if (nr > mid) ret = ret * query(nl, nr, mid + 1, r, (p << 1 | 1)) % mod;
  return ret;
}
void show() {
  for (int i = 1; i <= n; i++) printf("%lld ", query(i, i, 1, n, 1));
  puts("");
}
int main() {
  for (int i = 1; i < (200005 << 2); i++) a[i] = 1;
  cin >> n;
  sum[0] = 1;
  for (int i = 1; i <= n; i++)
    scanf("%lld", &arr[i]), sum[i] = sum[i - 1] * arr[i] % mod;
  cin >> m;
  for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].idx = i;
  sort(q + 1, q + 1 + m, cmp);
  int r = 1;
  for (int i = 1; i <= m; i++) {
    while (r <= q[i].r) {
      long long now = 1;
      for (int j = 1; j <= pcnt; j++) {
        bool flag = false;
        while (arr[r] % prime[j] == 0) arr[r] /= prime[j], flag = true;
        if (flag) {
          int& x = pre[prime[j]];
          if (x)
            update(x, 1, n, 1, qpow(prime[j] - 1, mod - 2) * prime[j] % mod);
          now = (now * (prime[j] - 1) % mod) * qpow(prime[j], mod - 2) % mod;
          x = r;
        }
      }
      if (arr[r] != 1) {
        int& x = pre[arr[r]];
        if (x) update(x, 1, n, 1, qpow(arr[r] - 1, mod - 2) * arr[r] % mod);
        now = (now * (arr[r] - 1) % mod) * qpow(arr[r], mod - 2) % mod;
        x = r;
      }
      update(r, 1, n, 1, now);
      ++r;
    }
    ans[q[i].idx] = (query(q[i].l, q[i].r, 1, n, 1) * sum[q[i].r] % mod) *
                    qpow(sum[q[i].l - 1], mod - 2) % mod;
  }
  for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
  return 0;
}

### Prompt

Your challenge is to write 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;
map<int, int> pre;
const long long mod = 1e9 + 7;
long long n, m, sum[200005], arr[200005], ans[200005], a[200005 << 2];
long long prime[205] = {
    0,   2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
    47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,  101, 103, 107, 109,
    113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
    197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
    281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373,
    379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
    463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
    571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
    659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
    761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
    863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
    977, 983, 991, 997};
long long pcnt = 168;
long long qpow(long long a, long long b) {
  long long ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) ret = ret * a % mod;
    a = a * a % mod;
  }
  return ret;
}
struct Query {
  int l, r, idx;
} q[200005];
bool cmp(const Query& a, const Query& b) { return a.r < b.r; }
void push_up(int p) { a[p] = a[(p << 1)] * a[(p << 1 | 1)] % mod; }
void update(int pos, int l, int r, int p, long long k) {
  if (l == r) {
    a[p] = a[p] * k % mod;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(pos, l, mid, (p << 1), k);
  else
    update(pos, mid + 1, r, (p << 1 | 1), k);
  push_up(p);
}
long long query(long long nl, long long nr, long long l, long long r,
                long long p) {
  if (nl <= l && r <= nr) return a[p];
  int mid = (l + r) >> 1;
  long long ret = 1;
  if (nl <= mid) ret = query(nl, nr, l, mid, (p << 1));
  if (nr > mid) ret = ret * query(nl, nr, mid + 1, r, (p << 1 | 1)) % mod;
  return ret;
}
void show() {
  for (int i = 1; i <= n; i++) printf("%lld ", query(i, i, 1, n, 1));
  puts("");
}
int main() {
  for (int i = 1; i < (200005 << 2); i++) a[i] = 1;
  cin >> n;
  sum[0] = 1;
  for (int i = 1; i <= n; i++)
    scanf("%lld", &arr[i]), sum[i] = sum[i - 1] * arr[i] % mod;
  cin >> m;
  for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].idx = i;
  sort(q + 1, q + 1 + m, cmp);
  int r = 1;
  for (int i = 1; i <= m; i++) {
    while (r <= q[i].r) {
      long long now = 1;
      for (int j = 1; j <= pcnt; j++) {
        bool flag = false;
        while (arr[r] % prime[j] == 0) arr[r] /= prime[j], flag = true;
        if (flag) {
          int& x = pre[prime[j]];
          if (x)
            update(x, 1, n, 1, qpow(prime[j] - 1, mod - 2) * prime[j] % mod);
          now = (now * (prime[j] - 1) % mod) * qpow(prime[j], mod - 2) % mod;
          x = r;
        }
      }
      if (arr[r] != 1) {
        int& x = pre[arr[r]];
        if (x) update(x, 1, n, 1, qpow(arr[r] - 1, mod - 2) * arr[r] % mod);
        now = (now * (arr[r] - 1) % mod) * qpow(arr[r], mod - 2) % mod;
        x = r;
      }
      update(r, 1, n, 1, now);
      ++r;
    }
    ans[q[i].idx] = (query(q[i].l, q[i].r, 1, n, 1) * sum[q[i].r] % mod) *
                    qpow(sum[q[i].l - 1], mod - 2) % mod;
  }
  for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
  return 0;
}

```