#include <bits/stdc++.h>
const int mod = 1e9 + 7;
using namespace std;
inline int read() {
  int x = 0, y = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return y ? -x : x;
}
template <typename T>
inline T read() {
  T x = 0;
  int y = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return y ? -x : x;
}
int mul[200005], a[200005], prime[200005], inv[200005], _inv[200005],
    last[200005], ans[200005], cnt, n;
bool is[1000005], vis[1000005];
vector<int> fac[1000005];
struct Query {
  int l, r, num;
  bool operator<(const Query &x) const { return r < x.r; }
} q[200005];
inline int INV(int x) {
  return x == 1 ? 1 : 1ll * (mod - mod / x) * INV(mod % x) % mod;
}
inline void add(int x, int d) {
  while (x <= n) mul[x] = 1ll * mul[x] * d % mod, x += (x & -x);
}
inline int ask(int x) {
  int ans = 1;
  while (x) ans = 1ll * ans * mul[x] % mod, x -= (x & -x);
  return ans;
}
signed main() {
  n = read();
  for (register int i = 1; i <= n; ++i) mul[i] = 1;
  for (register int i = 1; i <= n; ++i) add(i, a[i] = read()), vis[a[i]] = 1;
  for (register int i = 2; i <= 1000000; ++i) {
    if (!is[i]) {
      prime[++cnt] = i, inv[cnt] = INV(i), _inv[cnt] = INV(i - 1);
      for (register int j = i; j <= 1000000; j += i)
        if (vis[j]) fac[j].push_back(cnt);
    }
    for (register int j = 1; j <= cnt && i * prime[j] <= 1000000; ++j) {
      is[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  int m = read(), head = 1;
  for (register int i = 1; i <= m; ++i)
    q[i].l = read(), q[i].r = read(), q[i].num = i;
  sort(q + 1, q + 1 + m);
  for (register int i = 1; i <= n; ++i) {
    int S = 1, x;
    for (register int j = 0; j < fac[a[i]].size(); ++j) {
      x = fac[a[i]][j];
      S = 1ll * (prime[x] - 1) * inv[x] % mod * S % mod;
      if (last[x]) add(last[x], 1ll * prime[x] * _inv[x] % mod);
      last[x] = i;
    }
    if (S != 1) add(i, S);
    while (head <= m && q[head].r == i)
      ans[q[head].num] = 1ll * ask(i) * INV(ask(q[head].l - 1)) % mod, ++head;
  }
  for (register int i = 1; i <= m; ++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>
const int mod = 1e9 + 7;
using namespace std;
inline int read() {
  int x = 0, y = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return y ? -x : x;
}
template <typename T>
inline T read() {
  T x = 0;
  int y = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return y ? -x : x;
}
int mul[200005], a[200005], prime[200005], inv[200005], _inv[200005],
    last[200005], ans[200005], cnt, n;
bool is[1000005], vis[1000005];
vector<int> fac[1000005];
struct Query {
  int l, r, num;
  bool operator<(const Query &x) const { return r < x.r; }
} q[200005];
inline int INV(int x) {
  return x == 1 ? 1 : 1ll * (mod - mod / x) * INV(mod % x) % mod;
}
inline void add(int x, int d) {
  while (x <= n) mul[x] = 1ll * mul[x] * d % mod, x += (x & -x);
}
inline int ask(int x) {
  int ans = 1;
  while (x) ans = 1ll * ans * mul[x] % mod, x -= (x & -x);
  return ans;
}
signed main() {
  n = read();
  for (register int i = 1; i <= n; ++i) mul[i] = 1;
  for (register int i = 1; i <= n; ++i) add(i, a[i] = read()), vis[a[i]] = 1;
  for (register int i = 2; i <= 1000000; ++i) {
    if (!is[i]) {
      prime[++cnt] = i, inv[cnt] = INV(i), _inv[cnt] = INV(i - 1);
      for (register int j = i; j <= 1000000; j += i)
        if (vis[j]) fac[j].push_back(cnt);
    }
    for (register int j = 1; j <= cnt && i * prime[j] <= 1000000; ++j) {
      is[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  int m = read(), head = 1;
  for (register int i = 1; i <= m; ++i)
    q[i].l = read(), q[i].r = read(), q[i].num = i;
  sort(q + 1, q + 1 + m);
  for (register int i = 1; i <= n; ++i) {
    int S = 1, x;
    for (register int j = 0; j < fac[a[i]].size(); ++j) {
      x = fac[a[i]][j];
      S = 1ll * (prime[x] - 1) * inv[x] % mod * S % mod;
      if (last[x]) add(last[x], 1ll * prime[x] * _inv[x] % mod);
      last[x] = i;
    }
    if (S != 1) add(i, S);
    while (head <= m && q[head].r == i)
      ans[q[head].num] = 1ll * ask(i) * INV(ask(q[head].l - 1)) % mod, ++head;
  }
  for (register int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
}

```