#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int maxN = 1 << 20, maxTS = maxN * 2, mod = 1000000007;
template <class T1, class T2>
inline void addMod(T1& a, T2 b) {
  a = (a + b) % mod;
}
template <class T1, class T2>
inline void multMod(T1& a, T2 b) {
  a = a * b % mod;
}
long long qpow(long long a, long long b) {
  long long res0 = 1;
  for (; b != 0; b >>= 1) {
    if (b & 1) multMod(res0, a);
    multMod(a, a);
  }
  return res0;
}
template <class T1, class T2>
inline void divMod(T1& a, T2 b) {
  multMod(a, qpow(b, mod - 2));
}
struct Tree {
  int offset, qbegin, qend;
  long long T[maxTS], res;
  void qpriv(int v, int left, int right) {
    if (left >= qend or right <= qbegin) return;
    if (left >= qbegin and right <= qend) {
      multMod(res, T[v]);
      return;
    }
    qpriv(v * 2, left, (left + right) / 2);
    qpriv(v * 2 + 1, (left + right) / 2, right);
  }
  void init(long long* t, int n) {
    for (offset = 1; offset < n; offset *= 2)
      ;
    for (int i = (0); i < (int)(n); i++) T[offset + i] = t[i];
    for (int i = (n); i < (int)(offset); i++) T[offset + i] = 1ll;
    for (int i = offset - 1; i > (int)(0); i--)
      T[i] = T[i * 2] * T[i * 2 + 1] % mod;
  }
  void updt(int v, long long val) {
    for (v += offset; v != 0; v /= 2) multMod(T[v], val);
  }
  long long query(int a, int b) {
    qbegin = a + offset;
    qend = b + offset + 1;
    res = 1;
    qpriv(1, offset, offset * 2);
    return res;
  }
} tree;
long long apd[maxN], T[maxN], res[maxN];
vector<pair<int, int> > Qs[maxN];
vector<int> pos[maxN];
int it[maxN];
void sito() {
  for (int i = (1); i < (int)(maxN); i++) apd[i] = i;
  for (int i = 2; i * i < maxN; i++)
    if (apd[i] == i)
      for (int j = i * i; j < maxN; j += i) apd[j] = i;
}
long long f(int p) { return 1ll * (p - 1) * qpow(p, mod - 2) % mod; }
vector<int> primes(int n) {
  vector<int> ret(0);
  while (n != 1) {
    int p = apd[n];
    ret.push_back(p);
    while (n % p == 0) n /= p;
  }
  return ret;
}
void solve() {
  sito();
  int n;
  scanf("%d", &n);
  T[0] = T[n + 1] = 1ll;
  for (int i = (1); i < (int)(n + 1); i++) {
    scanf("%lld", T + i);
    for (int p : primes(T[i])) pos[p].push_back(i);
  }
  tree.init(T, n + 2);
  for (int i = (0); i < (int)(maxN); i++)
    if (!pos[i].empty()) {
      pos[i].push_back(n + 1);
      tree.updt(pos[i][0], f(i));
    }
  int q;
  scanf("%d", &q);
  for (int i = (0); i < (int)(q); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    Qs[a].push_back({b, i});
  }
  for (int i = (0); i < (int)(n + 1); i++) {
    for (auto p : Qs[i]) res[p.second] = tree.query(i, p.first);
    for (int p : primes(T[i])) tree.updt(pos[p][++it[p]], f(p));
  }
  for (int i = (0); i < (int)(q); i++) printf("%lld\n", res[i]);
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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("Ofast")
using namespace std;
const int maxN = 1 << 20, maxTS = maxN * 2, mod = 1000000007;
template <class T1, class T2>
inline void addMod(T1& a, T2 b) {
  a = (a + b) % mod;
}
template <class T1, class T2>
inline void multMod(T1& a, T2 b) {
  a = a * b % mod;
}
long long qpow(long long a, long long b) {
  long long res0 = 1;
  for (; b != 0; b >>= 1) {
    if (b & 1) multMod(res0, a);
    multMod(a, a);
  }
  return res0;
}
template <class T1, class T2>
inline void divMod(T1& a, T2 b) {
  multMod(a, qpow(b, mod - 2));
}
struct Tree {
  int offset, qbegin, qend;
  long long T[maxTS], res;
  void qpriv(int v, int left, int right) {
    if (left >= qend or right <= qbegin) return;
    if (left >= qbegin and right <= qend) {
      multMod(res, T[v]);
      return;
    }
    qpriv(v * 2, left, (left + right) / 2);
    qpriv(v * 2 + 1, (left + right) / 2, right);
  }
  void init(long long* t, int n) {
    for (offset = 1; offset < n; offset *= 2)
      ;
    for (int i = (0); i < (int)(n); i++) T[offset + i] = t[i];
    for (int i = (n); i < (int)(offset); i++) T[offset + i] = 1ll;
    for (int i = offset - 1; i > (int)(0); i--)
      T[i] = T[i * 2] * T[i * 2 + 1] % mod;
  }
  void updt(int v, long long val) {
    for (v += offset; v != 0; v /= 2) multMod(T[v], val);
  }
  long long query(int a, int b) {
    qbegin = a + offset;
    qend = b + offset + 1;
    res = 1;
    qpriv(1, offset, offset * 2);
    return res;
  }
} tree;
long long apd[maxN], T[maxN], res[maxN];
vector<pair<int, int> > Qs[maxN];
vector<int> pos[maxN];
int it[maxN];
void sito() {
  for (int i = (1); i < (int)(maxN); i++) apd[i] = i;
  for (int i = 2; i * i < maxN; i++)
    if (apd[i] == i)
      for (int j = i * i; j < maxN; j += i) apd[j] = i;
}
long long f(int p) { return 1ll * (p - 1) * qpow(p, mod - 2) % mod; }
vector<int> primes(int n) {
  vector<int> ret(0);
  while (n != 1) {
    int p = apd[n];
    ret.push_back(p);
    while (n % p == 0) n /= p;
  }
  return ret;
}
void solve() {
  sito();
  int n;
  scanf("%d", &n);
  T[0] = T[n + 1] = 1ll;
  for (int i = (1); i < (int)(n + 1); i++) {
    scanf("%lld", T + i);
    for (int p : primes(T[i])) pos[p].push_back(i);
  }
  tree.init(T, n + 2);
  for (int i = (0); i < (int)(maxN); i++)
    if (!pos[i].empty()) {
      pos[i].push_back(n + 1);
      tree.updt(pos[i][0], f(i));
    }
  int q;
  scanf("%d", &q);
  for (int i = (0); i < (int)(q); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    Qs[a].push_back({b, i});
  }
  for (int i = (0); i < (int)(n + 1); i++) {
    for (auto p : Qs[i]) res[p.second] = tree.query(i, p.first);
    for (int p : primes(T[i])) tree.updt(pos[p][++it[p]], f(p));
  }
  for (int i = (0); i < (int)(q); i++) printf("%lld\n", res[i]);
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}

```