#include <bits/stdc++.h>
using namespace std;
struct data {
  int l, r, id, ans;
} q[200500];
int a[200500], last[200500 * 10], pri[200500];
int t[3600009], inv[200500 * 10], vis[200500 * 10], mn[200500 * 10],
    mul[200500], r[3600009], b[3600009];
int n, m, tot, cnt;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int Pow(int x, long long y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1LL * ans * x % 1000000007;
    x = 1LL * x * x % 1000000007;
    y /= 2;
  }
  return ans;
}
void pre() {
  inv[1] = 1;
  for (int i = 2; i <= 1000000; i++) {
    if (!vis[i])
      vis[i] = 1, pri[++tot] = i, mn[i] = i, inv[i] = Pow(i, 1000000007 - 2);
    for (int j = 1; j <= tot; j++)
      if (i * pri[j] <= 1000000) {
        vis[i * pri[j]] = 1;
        mn[i * pri[j]] = pri[j];
        inv[i * pri[j]] = 1LL * inv[i] * inv[pri[j]] % 1000000007;
        if (i % pri[j] == 0) break;
      } else
        break;
  }
}
void add(int x, int y) {
  while (x <= cnt) {
    t[x] = (1LL * t[x] * y) % 1000000007;
    x += (x & (-x));
  }
}
int ask(int x) {
  int ans = 1;
  while (x) {
    ans = (1LL * ans * t[x]) % 1000000007;
    x -= (x & (-x));
  }
  return ans;
}
bool cmp(data a, data b) { return a.r < b.r; }
bool cmpid(data a, data b) { return a.id < b.id; }
int main() {
  pre();
  n = read();
  cnt = 0;
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    int x = a[i];
    while (x != 1) {
      int p = mn[x];
      while (x % p == 0) x /= p;
      b[++cnt] = p;
    }
    r[i] = cnt;
  }
  mul[0] = 1;
  for (int i = 1; i <= n; i++) mul[i] = 1LL * mul[i - 1] * a[i] % 1000000007;
  m = read();
  for (int i = 1; i <= m; i++) {
    q[i].l = read();
    q[i].r = read();
    q[i].id = i;
    q[i].ans = 1LL * mul[q[i].r] *
               Pow(mul[q[i].l - 1], 1LL * (1000000007 - 2)) % 1000000007;
    q[i].l = r[q[i].l - 1] + 1;
    q[i].r = r[q[i].r];
  }
  sort(q + 1, q + 1 + m, cmp);
  int now = 1;
  for (int i = 0; i <= cnt; i++) t[i] = 1;
  for (int i = 0; i <= cnt; i++) {
    int x = b[i];
    if (i) {
      if (!last[x])
        add(i, 1LL * (x - 1) * inv[x] % 1000000007);
      else {
        add(last[x], 1LL * x * inv[x - 1] % 1000000007);
        add(i, 1LL * (x - 1) * inv[x] % 1000000007);
      }
      last[x] = i;
    }
    while (now <= m && q[now].r == i) {
      if (q[now].l > q[now].r) {
        now++;
        continue;
      }
      int ans = ask(q[now].r);
      ans = 1LL * ans * Pow(ask(q[now].l - 1), 1LL * (1000000007 - 2)) %
            1000000007;
      q[now].ans = 1LL * q[now].ans * ans % 1000000007;
      now++;
    }
    if (now > m) break;
  }
  sort(q + 1, q + 1 + m, cmpid);
  for (int i = 1; i <= m; i++) printf("%d\n", q[i].ans);
  return 0;
}

### 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>
using namespace std;
struct data {
  int l, r, id, ans;
} q[200500];
int a[200500], last[200500 * 10], pri[200500];
int t[3600009], inv[200500 * 10], vis[200500 * 10], mn[200500 * 10],
    mul[200500], r[3600009], b[3600009];
int n, m, tot, cnt;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int Pow(int x, long long y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1LL * ans * x % 1000000007;
    x = 1LL * x * x % 1000000007;
    y /= 2;
  }
  return ans;
}
void pre() {
  inv[1] = 1;
  for (int i = 2; i <= 1000000; i++) {
    if (!vis[i])
      vis[i] = 1, pri[++tot] = i, mn[i] = i, inv[i] = Pow(i, 1000000007 - 2);
    for (int j = 1; j <= tot; j++)
      if (i * pri[j] <= 1000000) {
        vis[i * pri[j]] = 1;
        mn[i * pri[j]] = pri[j];
        inv[i * pri[j]] = 1LL * inv[i] * inv[pri[j]] % 1000000007;
        if (i % pri[j] == 0) break;
      } else
        break;
  }
}
void add(int x, int y) {
  while (x <= cnt) {
    t[x] = (1LL * t[x] * y) % 1000000007;
    x += (x & (-x));
  }
}
int ask(int x) {
  int ans = 1;
  while (x) {
    ans = (1LL * ans * t[x]) % 1000000007;
    x -= (x & (-x));
  }
  return ans;
}
bool cmp(data a, data b) { return a.r < b.r; }
bool cmpid(data a, data b) { return a.id < b.id; }
int main() {
  pre();
  n = read();
  cnt = 0;
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    int x = a[i];
    while (x != 1) {
      int p = mn[x];
      while (x % p == 0) x /= p;
      b[++cnt] = p;
    }
    r[i] = cnt;
  }
  mul[0] = 1;
  for (int i = 1; i <= n; i++) mul[i] = 1LL * mul[i - 1] * a[i] % 1000000007;
  m = read();
  for (int i = 1; i <= m; i++) {
    q[i].l = read();
    q[i].r = read();
    q[i].id = i;
    q[i].ans = 1LL * mul[q[i].r] *
               Pow(mul[q[i].l - 1], 1LL * (1000000007 - 2)) % 1000000007;
    q[i].l = r[q[i].l - 1] + 1;
    q[i].r = r[q[i].r];
  }
  sort(q + 1, q + 1 + m, cmp);
  int now = 1;
  for (int i = 0; i <= cnt; i++) t[i] = 1;
  for (int i = 0; i <= cnt; i++) {
    int x = b[i];
    if (i) {
      if (!last[x])
        add(i, 1LL * (x - 1) * inv[x] % 1000000007);
      else {
        add(last[x], 1LL * x * inv[x - 1] % 1000000007);
        add(i, 1LL * (x - 1) * inv[x] % 1000000007);
      }
      last[x] = i;
    }
    while (now <= m && q[now].r == i) {
      if (q[now].l > q[now].r) {
        now++;
        continue;
      }
      int ans = ask(q[now].r);
      ans = 1LL * ans * Pow(ask(q[now].l - 1), 1LL * (1000000007 - 2)) %
            1000000007;
      q[now].ans = 1LL * q[now].ans * ans % 1000000007;
      now++;
    }
    if (now > m) break;
  }
  sort(q + 1, q + 1 + m, cmpid);
  for (int i = 1; i <= m; i++) printf("%d\n", q[i].ans);
  return 0;
}

```