#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const int M = 1 << 18;
long long qpot(long long a, long long b) {
  if (a == 0) return 0;
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    b /= 2;
    a = (a * a) % MOD;
  }
  return res;
}
long long odwroc(long long a) { return qpot(a, MOD - 2); }
vector<long long> primes;
int sito[1000006];
long long f[1000006];
long long fu[1000006];
long long tab[200006];
long long pref[200006];
long long wynik[200006];
vector<pair<long long, long long> > graf[200006];
vector<long long> in_graf[200006];
long long wszystko = 1;
vector<pair<long long, long long> > zapytania[200006];
vector<long long> pozycje[1000006];
long long d[2 * M + 5];
vector<long long> factor(int n) {
  vector<long long> v;
  while (n > 1) {
    while (n > 1 && (!v.empty() && v.back() == sito[n])) {
      n /= sito[n];
    }
    if (n > 1 && (v.empty() || v.back() != sito[n])) {
      v.push_back(sito[n]);
      n /= sito[n];
    }
  }
  return v;
}
void zrob_fu() {
  for (int p : primes) {
    f[p] = ((p - 1) * odwroc(p)) % MOD;
    fu[p] = odwroc(f[p]);
  }
}
void ustaw_drzewo(int n) {
  for (auto i = (1); i <= (n); ++i) {
    vector<long long> v = factor(tab[i]);
    for (auto p : v) {
      pozycje[p].push_back(i);
    }
  }
  for (int p : primes) {
    if (!pozycje[p].empty()) {
      graf[0].push_back(make_pair(pozycje[p][0], p));
      graf[pozycje[p].back()].push_back(make_pair(n + 1, p));
      wszystko = (wszystko * f[p]) % MOD;
    }
    for (auto i = (0); i <= (((int)((pozycje[p]).size()) - 1) - 1); ++i) {
      graf[pozycje[p][i]].push_back(make_pair(pozycje[p][i + 1], p));
    }
  }
}
void inicjalizuj() {
  for (auto i = (0); i <= ((2 * M) - 1); ++i) d[i] = 1;
}
void wystaw(int pos, long long p) {
  pos += M;
  while (pos) {
    d[pos] = (d[pos] * fu[p]) % MOD;
    pos /= 2;
  }
}
void wstaw(int pos, long long p) {
  pos += M;
  while (pos) {
    d[pos] = (d[pos] * f[p]) % MOD;
    pos /= 2;
  }
}
long long zapytaj(long long pocz, long long kon) {
  if (pocz > kon) return 1;
  pocz += M;
  kon += M;
  long long res = d[pocz];
  if (pocz != kon) res = (res * d[kon]) % MOD;
  while (pocz / 2 != kon / 2) {
    if (!(pocz & 1)) res = (res * d[pocz ^ 1]) % MOD;
    if (kon & 1) res = (res * d[kon ^ 1]) % MOD;
    pocz /= 2;
    kon /= 2;
  }
  return res;
}
void solve(int n) {
  for (auto pp : graf[0]) wstaw(pp.first, pp.second);
  for (auto i = (1); i <= (n); ++i) {
    for (auto zap : zapytania[i]) {
      wynik[zap.second] =
          (wynik[zap.second] * odwroc(zapytaj(zap.first + 1, n + 1))) % MOD;
    }
    for (auto pp : graf[i]) {
      wystaw(i, pp.second);
      wstaw(pp.first, pp.second);
    }
  }
}
void jebaj() {
  int n;
  cin >> n;
  pref[0] = 1;
  for (auto i = (1); i <= (n); ++i) {
    cin >> tab[i];
    pref[i] = (pref[i - 1] * tab[i]) % MOD;
  }
  ustaw_drzewo(n);
  int q;
  cin >> q;
  for (auto i = (0); i <= ((q)-1); ++i) {
    int a, b;
    cin >> a >> b;
    wynik[i] = (pref[b] * odwroc(pref[a - 1])) % MOD;
    wynik[i] = (wynik[i] * wszystko) % MOD;
    zapytania[a].push_back(make_pair(b, i));
  }
  solve(n);
  for (auto i = (0); i <= ((q)-1); ++i) cout << wynik[i] << "\n";
}
void prepro() {
  for (auto i = (2); i <= (1000000); ++i) {
    if (!sito[i]) {
      primes.push_back(i);
      for (int j = i; j <= 1000000; j += i) sito[j] = i;
    }
  }
  inicjalizuj();
  zrob_fu();
}
int main() {
  prepro();
  ios_base::sync_with_stdio(0);
  int t = 1;
  for (auto i = (0); i <= ((t)-1); ++i) {
    jebaj();
  }
}

### Prompt

Generate 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;
const long long MOD = 1e9 + 7;
const int M = 1 << 18;
long long qpot(long long a, long long b) {
  if (a == 0) return 0;
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    b /= 2;
    a = (a * a) % MOD;
  }
  return res;
}
long long odwroc(long long a) { return qpot(a, MOD - 2); }
vector<long long> primes;
int sito[1000006];
long long f[1000006];
long long fu[1000006];
long long tab[200006];
long long pref[200006];
long long wynik[200006];
vector<pair<long long, long long> > graf[200006];
vector<long long> in_graf[200006];
long long wszystko = 1;
vector<pair<long long, long long> > zapytania[200006];
vector<long long> pozycje[1000006];
long long d[2 * M + 5];
vector<long long> factor(int n) {
  vector<long long> v;
  while (n > 1) {
    while (n > 1 && (!v.empty() && v.back() == sito[n])) {
      n /= sito[n];
    }
    if (n > 1 && (v.empty() || v.back() != sito[n])) {
      v.push_back(sito[n]);
      n /= sito[n];
    }
  }
  return v;
}
void zrob_fu() {
  for (int p : primes) {
    f[p] = ((p - 1) * odwroc(p)) % MOD;
    fu[p] = odwroc(f[p]);
  }
}
void ustaw_drzewo(int n) {
  for (auto i = (1); i <= (n); ++i) {
    vector<long long> v = factor(tab[i]);
    for (auto p : v) {
      pozycje[p].push_back(i);
    }
  }
  for (int p : primes) {
    if (!pozycje[p].empty()) {
      graf[0].push_back(make_pair(pozycje[p][0], p));
      graf[pozycje[p].back()].push_back(make_pair(n + 1, p));
      wszystko = (wszystko * f[p]) % MOD;
    }
    for (auto i = (0); i <= (((int)((pozycje[p]).size()) - 1) - 1); ++i) {
      graf[pozycje[p][i]].push_back(make_pair(pozycje[p][i + 1], p));
    }
  }
}
void inicjalizuj() {
  for (auto i = (0); i <= ((2 * M) - 1); ++i) d[i] = 1;
}
void wystaw(int pos, long long p) {
  pos += M;
  while (pos) {
    d[pos] = (d[pos] * fu[p]) % MOD;
    pos /= 2;
  }
}
void wstaw(int pos, long long p) {
  pos += M;
  while (pos) {
    d[pos] = (d[pos] * f[p]) % MOD;
    pos /= 2;
  }
}
long long zapytaj(long long pocz, long long kon) {
  if (pocz > kon) return 1;
  pocz += M;
  kon += M;
  long long res = d[pocz];
  if (pocz != kon) res = (res * d[kon]) % MOD;
  while (pocz / 2 != kon / 2) {
    if (!(pocz & 1)) res = (res * d[pocz ^ 1]) % MOD;
    if (kon & 1) res = (res * d[kon ^ 1]) % MOD;
    pocz /= 2;
    kon /= 2;
  }
  return res;
}
void solve(int n) {
  for (auto pp : graf[0]) wstaw(pp.first, pp.second);
  for (auto i = (1); i <= (n); ++i) {
    for (auto zap : zapytania[i]) {
      wynik[zap.second] =
          (wynik[zap.second] * odwroc(zapytaj(zap.first + 1, n + 1))) % MOD;
    }
    for (auto pp : graf[i]) {
      wystaw(i, pp.second);
      wstaw(pp.first, pp.second);
    }
  }
}
void jebaj() {
  int n;
  cin >> n;
  pref[0] = 1;
  for (auto i = (1); i <= (n); ++i) {
    cin >> tab[i];
    pref[i] = (pref[i - 1] * tab[i]) % MOD;
  }
  ustaw_drzewo(n);
  int q;
  cin >> q;
  for (auto i = (0); i <= ((q)-1); ++i) {
    int a, b;
    cin >> a >> b;
    wynik[i] = (pref[b] * odwroc(pref[a - 1])) % MOD;
    wynik[i] = (wynik[i] * wszystko) % MOD;
    zapytania[a].push_back(make_pair(b, i));
  }
  solve(n);
  for (auto i = (0); i <= ((q)-1); ++i) cout << wynik[i] << "\n";
}
void prepro() {
  for (auto i = (2); i <= (1000000); ++i) {
    if (!sito[i]) {
      primes.push_back(i);
      for (int j = i; j <= 1000000; j += i) sito[j] = i;
    }
  }
  inicjalizuj();
  zrob_fu();
}
int main() {
  prepro();
  ios_base::sync_with_stdio(0);
  int t = 1;
  for (auto i = (0); i <= ((t)-1); ++i) {
    jebaj();
  }
}

```