#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int N = 2e5 + 5;
constexpr LL MOD = 1e9 + 7;
constexpr int maxv = 1e6 + 100;
int n, q;
int a[N], last[maxv];
vector<pair<int, int>> dat[N];
int ans[N];
bitset<maxv> status;
vector<int> primes;
LL fen[N];
LL power(LL a, int b) {
  LL rev = 1;
  while (b) {
    if (b & 1) rev = rev * a % MOD;
    a = a * a % MOD;
    b /= 2;
  }
  return rev;
}
void update(int k, int val) {
  while (k < N) {
    (fen[k] *= val) %= MOD;
    k += k & -k;
  }
}
LL query(int k) {
  LL rev = 1;
  while (k > 0) {
    (rev *= fen[k]) %= MOD;
    k -= k & -k;
  }
  return rev;
}
void gen() {
  for (int p = 2; p * p < maxv; p++) {
    if (!status[p]) {
      primes.push_back(p);
      for (int j = p * 2; j < maxv; j += p) status[j] = 1;
    }
  }
}
void load() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    dat[r].push_back({l, i});
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  fill(begin(fen), end(fen), 1);
  gen();
  load();
  for (int i = 1; i <= n; i++) {
    update(i, a[i]);
    for (const auto& p : primes) {
      if (a[i] % p == 0) {
        if (last[p]) update(last[p], p * power(p - 1, MOD - 2) % MOD);
        update(i, (p - 1) * power(p, MOD - 2) % MOD);
        last[p] = i;
        while (a[i] % p == 0) a[i] /= p;
      }
    }
    if (a[i] > 1) {
      if (last[a[i]]) update(last[a[i]], a[i] * power(a[i] - 1, MOD - 2) % MOD);
      last[a[i]] = i;
      update(i, (a[i] - 1) * power(a[i], MOD - 2) % MOD);
    }
    for (auto x : dat[i]) {
      ans[x.second] = query(i) * power(query(x.first - 1), MOD - 2) % MOD;
    }
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

### Prompt

In CPP, your task is to solve 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;
using LL = long long;
constexpr int N = 2e5 + 5;
constexpr LL MOD = 1e9 + 7;
constexpr int maxv = 1e6 + 100;
int n, q;
int a[N], last[maxv];
vector<pair<int, int>> dat[N];
int ans[N];
bitset<maxv> status;
vector<int> primes;
LL fen[N];
LL power(LL a, int b) {
  LL rev = 1;
  while (b) {
    if (b & 1) rev = rev * a % MOD;
    a = a * a % MOD;
    b /= 2;
  }
  return rev;
}
void update(int k, int val) {
  while (k < N) {
    (fen[k] *= val) %= MOD;
    k += k & -k;
  }
}
LL query(int k) {
  LL rev = 1;
  while (k > 0) {
    (rev *= fen[k]) %= MOD;
    k -= k & -k;
  }
  return rev;
}
void gen() {
  for (int p = 2; p * p < maxv; p++) {
    if (!status[p]) {
      primes.push_back(p);
      for (int j = p * 2; j < maxv; j += p) status[j] = 1;
    }
  }
}
void load() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    dat[r].push_back({l, i});
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  fill(begin(fen), end(fen), 1);
  gen();
  load();
  for (int i = 1; i <= n; i++) {
    update(i, a[i]);
    for (const auto& p : primes) {
      if (a[i] % p == 0) {
        if (last[p]) update(last[p], p * power(p - 1, MOD - 2) % MOD);
        update(i, (p - 1) * power(p, MOD - 2) % MOD);
        last[p] = i;
        while (a[i] % p == 0) a[i] /= p;
      }
    }
    if (a[i] > 1) {
      if (last[a[i]]) update(last[a[i]], a[i] * power(a[i] - 1, MOD - 2) % MOD);
      last[a[i]] = i;
      update(i, (a[i] - 1) * power(a[i], MOD - 2) % MOD);
    }
    for (auto x : dat[i]) {
      ans[x.second] = query(i) * power(query(x.first - 1), MOD - 2) % MOD;
    }
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

```