#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 11, mod = 1e9 + 7, mx = 2e6;
long long t[maxn * 4], pr[mx + 11], ob[mx + 111], lp[mx + 111], last[mx + 111],
    ans[maxn];
int n, m, a[maxn];
vector<pair<int, int> > q[maxn];
long long bp(long long a, long long n) {
  if (n == 0) return 1LL;
  long long res = bp(a, n / 2) % mod;
  res = (res * res) % mod;
  if (n & 1) res = (res * a) % mod;
  return res;
}
void precalc() {
  for (int i = 2; i < mx; i += 2) lp[i] = 2;
  for (int i = 3; i * i < mx; i += 2) {
    if (!lp[i]) {
      for (int j = i * i; j < mx; j += i + i) lp[j] = i;
    }
  }
  for (int i = 3; i < mx; i += 2)
    if (!lp[i]) lp[i] = i;
  for (int i = 2; i < mx; i++)
    if (lp[i] == i) {
      pr[i] = ((i - 1) * bp(i, mod - 2)) % mod;
      ob[i] = (i * bp(i - 1, mod - 2)) % mod;
    }
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v + v, tl, tm);
  build(v + v + 1, tm + 1, tr);
  t[v] = (t[v + v] * t[v + v + 1]) % mod;
}
void update(int v, int tl, int tr, int pos, int val) {
  if (tl == tr) {
    t[v] = (t[v] * val) % mod;
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm)
    update(v + v, tl, tm, pos, val);
  else
    update(v + v + 1, tm + 1, tr, pos, val);
  t[v] = (t[v + v] * t[v + v + 1]) % mod;
}
long long get(int v, int tl, int tr, int l, int r) {
  if (l > r) return 1;
  if (tl == l && tr == r) return t[v];
  int tm = (tl + tr) / 2;
  return (get(v + v, tl, tm, l, min(r, tm)) *
          get(v + v + 1, tm + 1, tr, max(l, tm + 1), r)) %
         mod;
}
int main() {
  precalc();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    q[r].push_back(make_pair(l, i));
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int x = a[i];
    long long res = 1;
    while (x > 1) {
      int p = lp[x];
      if (last[p]) update(1, 1, n, last[p], ob[p]);
      last[p] = i;
      res = res * pr[p] % mod;
      while (x % p == 0) x /= p;
    }
    update(1, 1, n, i, res);
    for (int j = 0; j < q[i].size(); j++) {
      int cur = q[i][j].second;
      int l = q[i][j].first;
      ans[cur] = get(1, 1, n, l, i);
    }
  }
  for (int i = 1; i <= m; i++) printf("%I64d\n", ans[i]);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 maxn = 3e5 + 11, mod = 1e9 + 7, mx = 2e6;
long long t[maxn * 4], pr[mx + 11], ob[mx + 111], lp[mx + 111], last[mx + 111],
    ans[maxn];
int n, m, a[maxn];
vector<pair<int, int> > q[maxn];
long long bp(long long a, long long n) {
  if (n == 0) return 1LL;
  long long res = bp(a, n / 2) % mod;
  res = (res * res) % mod;
  if (n & 1) res = (res * a) % mod;
  return res;
}
void precalc() {
  for (int i = 2; i < mx; i += 2) lp[i] = 2;
  for (int i = 3; i * i < mx; i += 2) {
    if (!lp[i]) {
      for (int j = i * i; j < mx; j += i + i) lp[j] = i;
    }
  }
  for (int i = 3; i < mx; i += 2)
    if (!lp[i]) lp[i] = i;
  for (int i = 2; i < mx; i++)
    if (lp[i] == i) {
      pr[i] = ((i - 1) * bp(i, mod - 2)) % mod;
      ob[i] = (i * bp(i - 1, mod - 2)) % mod;
    }
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v + v, tl, tm);
  build(v + v + 1, tm + 1, tr);
  t[v] = (t[v + v] * t[v + v + 1]) % mod;
}
void update(int v, int tl, int tr, int pos, int val) {
  if (tl == tr) {
    t[v] = (t[v] * val) % mod;
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm)
    update(v + v, tl, tm, pos, val);
  else
    update(v + v + 1, tm + 1, tr, pos, val);
  t[v] = (t[v + v] * t[v + v + 1]) % mod;
}
long long get(int v, int tl, int tr, int l, int r) {
  if (l > r) return 1;
  if (tl == l && tr == r) return t[v];
  int tm = (tl + tr) / 2;
  return (get(v + v, tl, tm, l, min(r, tm)) *
          get(v + v + 1, tm + 1, tr, max(l, tm + 1), r)) %
         mod;
}
int main() {
  precalc();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    q[r].push_back(make_pair(l, i));
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int x = a[i];
    long long res = 1;
    while (x > 1) {
      int p = lp[x];
      if (last[p]) update(1, 1, n, last[p], ob[p]);
      last[p] = i;
      res = res * pr[p] % mod;
      while (x % p == 0) x /= p;
    }
    update(1, 1, n, i, res);
    for (int j = 0; j < q[i].size(); j++) {
      int cur = q[i][j].second;
      int l = q[i][j].first;
      ans[cur] = get(1, 1, n, l, i);
    }
  }
  for (int i = 1; i <= m; i++) printf("%I64d\n", ans[i]);
  return 0;
}

```