#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int MAX = 1000005;
const int md = 1000000007;
int ans[N], a[N], bt[N], prime[MAX], last[MAX], n;
vector<pair<int, int> > q[N];
int mul(int x, int y) { return (long long)x * y % md; }
int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}
int inv(int x) { return power(x, md - 2); }
void update(int i, int v) {
  while (i <= n) {
    bt[i] = mul(bt[i], v);
    i += i & -i;
  }
}
int get(int i) {
  int res = 1;
  while (i > 0) {
    res = mul(res, bt[i]);
    i -= i & -i;
  }
  return res;
}
void sieve() {
  for (int i = 0; i < MAX; i++) {
    prime[i] = i;
  }
  prime[0] = prime[1] = 1;
  for (int i = 4; i < MAX; i += 2) {
    prime[i] = 2;
  }
  for (int i = 3; i * i < MAX; i += 2) {
    if (prime[i] == i) {
      for (int j = i * i; j < MAX; j += 2 * i) {
        prime[j] = i;
      }
    }
  }
}
int main() {
  int ddd = 3;
  int dddd = inv(3);
  sieve();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    q[y].push_back(make_pair(i, x));
  }
  for (int i = 0; i < N; i++) {
    bt[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    int cur = a[i];
    while (cur > 1) {
      int pr = prime[cur];
      if (last[pr]) {
        update(last[pr], mul(pr, inv(pr - 1)));
      }
      last[pr] = i;
      update(i, mul((pr - 1), inv(pr)));
      while (cur % pr == 0) {
        cur /= pr;
      }
    }
    update(i, a[i]);
    for (int j = 0; j < q[i].size(); j++) {
      int id = q[i][j].first;
      int l = q[i][j].second;
      ans[id] = mul(get(i), inv(get(l - 1)));
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%d\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 N = 200005;
const int MAX = 1000005;
const int md = 1000000007;
int ans[N], a[N], bt[N], prime[MAX], last[MAX], n;
vector<pair<int, int> > q[N];
int mul(int x, int y) { return (long long)x * y % md; }
int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}
int inv(int x) { return power(x, md - 2); }
void update(int i, int v) {
  while (i <= n) {
    bt[i] = mul(bt[i], v);
    i += i & -i;
  }
}
int get(int i) {
  int res = 1;
  while (i > 0) {
    res = mul(res, bt[i]);
    i -= i & -i;
  }
  return res;
}
void sieve() {
  for (int i = 0; i < MAX; i++) {
    prime[i] = i;
  }
  prime[0] = prime[1] = 1;
  for (int i = 4; i < MAX; i += 2) {
    prime[i] = 2;
  }
  for (int i = 3; i * i < MAX; i += 2) {
    if (prime[i] == i) {
      for (int j = i * i; j < MAX; j += 2 * i) {
        prime[j] = i;
      }
    }
  }
}
int main() {
  int ddd = 3;
  int dddd = inv(3);
  sieve();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    q[y].push_back(make_pair(i, x));
  }
  for (int i = 0; i < N; i++) {
    bt[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    int cur = a[i];
    while (cur > 1) {
      int pr = prime[cur];
      if (last[pr]) {
        update(last[pr], mul(pr, inv(pr - 1)));
      }
      last[pr] = i;
      update(i, mul((pr - 1), inv(pr)));
      while (cur % pr == 0) {
        cur /= pr;
      }
    }
    update(i, a[i]);
    for (int j = 0; j < q[i].size(); j++) {
      int id = q[i][j].first;
      int l = q[i][j].second;
      ans[id] = mul(get(i), inv(get(l - 1)));
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

```