#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1, M = 1e9 + 7;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
int n, q, bit[N], inv[N], a[N], last[N], INVER[N], ans[N];
bool prime[N];
vector<int> v[N];
struct query {
  int l, r, id;
  void sc(int temp) {
    scanf("%d%d", &l, &r);
    id = temp;
  }
} Q[N];
int power(int base, int to) {
  int ret = 1;
  while (to) {
    if (to & 1) ret = ret * 1LL * base % M;
    to >>= 1;
    base = base * 1LL * base % M;
  }
  return ret;
}
int INV(int a) {
  if (INVER[a] != -1) return INVER[a];
  return INVER[a] = power(a, M - 2);
}
void add(int at, int *bit, int val) {
  for (; at < N; at += (-at) & at) bit[at] = bit[at] * 1LL * val % M;
}
int get(int at, int *bit) {
  int ret = 1;
  for (; at; at -= at & (-at)) ret = ret * 1LL * bit[at] % M;
  return ret;
}
int main() {
  for (int i = 0; i < N; i++) bit[i] = inv[i] = 1;
  memset(last, -1, sizeof last);
  memset(INVER, -1, sizeof INVER);
  scanf("%d", &n);
  for (int i = 2; i < N; i++)
    if (!prime[i]) {
      for (int j = i; j < N; j += i) {
        prime[j] = 1;
        v[j].push_back(i);
      }
    }
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) Q[i].sc(i);
  sort(Q, Q + q, [&](query a, query b) { return a.r < b.r; });
  int j = 1;
  for (int i = 0; i < q; i++) {
    while (j <= Q[i].r) {
      add(j, bit, a[j]);
      add(j, inv, INV(a[j]));
      for (auto k : v[a[j]]) {
        if (last[k] != -1) {
          add(last[k], bit, INV(k - 1) * 1LL * k % M);
          add(last[k], inv, (k - 1LL) * INV(k) % M);
        }
        last[k] = j;
        add(last[k], bit, (k - 1LL) * INV(k) % M);
        add(last[k], inv, k * 1LL * INV(k - 1) % M);
      }
      j++;
    }
    ans[Q[i].id] = get(Q[i].r, bit);
    ans[Q[i].id] = ans[Q[i].id] * 1LL * get(Q[i].l - 1, inv) % M;
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}

### 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>
using namespace std;
const int N = 1e6 + 1, M = 1e9 + 7;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
int n, q, bit[N], inv[N], a[N], last[N], INVER[N], ans[N];
bool prime[N];
vector<int> v[N];
struct query {
  int l, r, id;
  void sc(int temp) {
    scanf("%d%d", &l, &r);
    id = temp;
  }
} Q[N];
int power(int base, int to) {
  int ret = 1;
  while (to) {
    if (to & 1) ret = ret * 1LL * base % M;
    to >>= 1;
    base = base * 1LL * base % M;
  }
  return ret;
}
int INV(int a) {
  if (INVER[a] != -1) return INVER[a];
  return INVER[a] = power(a, M - 2);
}
void add(int at, int *bit, int val) {
  for (; at < N; at += (-at) & at) bit[at] = bit[at] * 1LL * val % M;
}
int get(int at, int *bit) {
  int ret = 1;
  for (; at; at -= at & (-at)) ret = ret * 1LL * bit[at] % M;
  return ret;
}
int main() {
  for (int i = 0; i < N; i++) bit[i] = inv[i] = 1;
  memset(last, -1, sizeof last);
  memset(INVER, -1, sizeof INVER);
  scanf("%d", &n);
  for (int i = 2; i < N; i++)
    if (!prime[i]) {
      for (int j = i; j < N; j += i) {
        prime[j] = 1;
        v[j].push_back(i);
      }
    }
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) Q[i].sc(i);
  sort(Q, Q + q, [&](query a, query b) { return a.r < b.r; });
  int j = 1;
  for (int i = 0; i < q; i++) {
    while (j <= Q[i].r) {
      add(j, bit, a[j]);
      add(j, inv, INV(a[j]));
      for (auto k : v[a[j]]) {
        if (last[k] != -1) {
          add(last[k], bit, INV(k - 1) * 1LL * k % M);
          add(last[k], inv, (k - 1LL) * INV(k) % M);
        }
        last[k] = j;
        add(last[k], bit, (k - 1LL) * INV(k) % M);
        add(last[k], inv, k * 1LL * INV(k - 1) % M);
      }
      j++;
    }
    ans[Q[i].id] = get(Q[i].r, bit);
    ans[Q[i].id] = ans[Q[i].id] * 1LL * get(Q[i].l - 1, inv) % M;
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}

```