#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
vector<pair<int, int> > v[N];
int las[N], p[N], is[N];
int in[N], in2[N], mp[N];
int n, q, pcnt, a[N], ans[N], f[N];
int inc(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int dec(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int ksm(int a, int b = mod - 2, int ans = 1) {
  for (; b; a = mul(a, a), b >>= 1)
    if (b & 1) ans = mul(ans, a);
  return ans;
}
void init(int n) {
  for (int i = 2; i <= n; i++) {
    if (!is[i])
      p[++pcnt] = i, in[i] = ksm(i), in2[i] = ksm(i - 1), mp[i] = pcnt;
    for (int j = 1; j <= pcnt and p[j] * i <= n; j++) {
      is[p[j] * i] = 1;
      if (i % p[j] == 0) break;
    }
  }
}
void add(int x, int y) {
  while (x <= n) f[x] = mul(f[x], y), x += x & -x;
}
int query(int x, int ans = 1) {
  while (x) ans = mul(ans, f[x]), x -= x & -x;
  return ans;
}
signed main() {
  init(N - 5);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &q);
  for (int a, b, i = 1; i <= q; i++)
    scanf("%d%d", &a, &b), v[b].push_back(pair<int, int>(a, i));
  for (int i = 1; i <= n; i++) f[i] = 1;
  for (int i = 1; i <= n; i++) {
    int now = a[i];
    for (int j = 1; j <= pcnt and p[j] <= now; j++) {
      if (!is[now]) j = mp[now];
      if (now % p[j] == 0) {
        int t = 1;
        while (now % p[j] == 0) now /= p[j], t *= p[j];
        add(i, t / p[j] * (p[j] - 1));
        if (las[p[j]]) add(las[p[j]], mul(p[j], in2[p[j]]));
        las[p[j]] = i;
      }
    }
    for (auto x : v[i]) ans[x.second] = mul(query(i), ksm(query(x.first - 1)));
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

### 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>
#pragma GCC optimize(2)
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
vector<pair<int, int> > v[N];
int las[N], p[N], is[N];
int in[N], in2[N], mp[N];
int n, q, pcnt, a[N], ans[N], f[N];
int inc(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int dec(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int ksm(int a, int b = mod - 2, int ans = 1) {
  for (; b; a = mul(a, a), b >>= 1)
    if (b & 1) ans = mul(ans, a);
  return ans;
}
void init(int n) {
  for (int i = 2; i <= n; i++) {
    if (!is[i])
      p[++pcnt] = i, in[i] = ksm(i), in2[i] = ksm(i - 1), mp[i] = pcnt;
    for (int j = 1; j <= pcnt and p[j] * i <= n; j++) {
      is[p[j] * i] = 1;
      if (i % p[j] == 0) break;
    }
  }
}
void add(int x, int y) {
  while (x <= n) f[x] = mul(f[x], y), x += x & -x;
}
int query(int x, int ans = 1) {
  while (x) ans = mul(ans, f[x]), x -= x & -x;
  return ans;
}
signed main() {
  init(N - 5);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &q);
  for (int a, b, i = 1; i <= q; i++)
    scanf("%d%d", &a, &b), v[b].push_back(pair<int, int>(a, i));
  for (int i = 1; i <= n; i++) f[i] = 1;
  for (int i = 1; i <= n; i++) {
    int now = a[i];
    for (int j = 1; j <= pcnt and p[j] <= now; j++) {
      if (!is[now]) j = mp[now];
      if (now % p[j] == 0) {
        int t = 1;
        while (now % p[j] == 0) now /= p[j], t *= p[j];
        add(i, t / p[j] * (p[j] - 1));
        if (las[p[j]]) add(las[p[j]], mul(p[j], in2[p[j]]));
        las[p[j]] = i;
      }
    }
    for (auto x : v[i]) ans[x.second] = mul(query(i), ksm(query(x.first - 1)));
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

```