#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int INF = 1000000001;
const long long int LLINF = 1000000000000000001LL;
const int ROOT = 500;
const int N = 1000002;
const int NN = 200004;
int Sieve[N];
long long int Rev[N];
int Sth[N];
int RevSth[N];
void pre() {
  for (int i = (2); i <= (N - 1); ++i) Sieve[i] = i;
  for (int i = (2); i <= (N - 1); ++i)
    if (Sieve[i] == i)
      for (int j = 2 * i; j < N; j += i) Sieve[j] = min(Sieve[j], i);
  Rev[1] = 1;
  for (int i = (2); i <= (N - 1); ++i) {
    Rev[i] = -(MOD / i) * Rev[MOD % i];
    Rev[i] = (MOD + Rev[i] % MOD) % MOD;
  }
  for (int i = (1); i <= (N - 1); ++i)
    if (Sieve[i] == i) {
      Sth[i] = ((i - 1) * Rev[i]) % MOD;
      RevSth[i] = (Rev[i - 1] * i) % MOD;
    }
}
struct inter {
  pair<int, int> pr;
  int id;
};
bool comp(const inter &x, const inter &y) {
  if (x.pr.second / ROOT != y.pr.second / ROOT)
    return x.pr.second < y.pr.second;
  else {
    if ((x.pr.second / ROOT) & 1)
      return x.pr.first > y.pr.first;
    else
      return x.pr.first < y.pr.first;
  }
}
int ans = 1;
int cnt[N];
int T[NN];
vector<int> primes[NN];
void addPrimes(int i) {
  ans = ((long long int)ans * T[i]) % MOD;
  for (auto p : primes[i]) {
    if (!cnt[p]) ans = ((long long int)ans * Sth[p]) % MOD;
    cnt[p]++;
  }
}
void removePrimes(int i) {
  ans = ((long long int)ans * Rev[T[i]]) % MOD;
  for (auto p : primes[i]) {
    cnt[p]--;
    if (!cnt[p]) ans = ((long long int)ans * RevSth[p]) % MOD;
  }
}
inter Q[NN];
int answer[NN];
inline void fastRead_int(int &x) {
  register int c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
int main() {
  pre();
  int n;
  scanf("%d", &n);
  for (int i = (0); i <= (n - 1); ++i) scanf("%d", T + i);
  for (int i = (0); i <= (n - 1); ++i) {
    int x = T[i];
    primes[i].reserve(10);
    while (x > 1) {
      int p = Sieve[x];
      primes[i].push_back(p);
      while (x % p == 0) x /= p;
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = (0); i <= (q - 1); ++i) {
    fastRead_int(Q[i].pr.first);
    fastRead_int(Q[i].pr.second);
    ;
    Q[i].pr.first--;
    Q[i].pr.second--;
    Q[i].id = i;
  }
  sort(Q, Q + q, comp);
  int L = 0, R = -1;
  for (int i = (0); i <= (q - 1); ++i) {
    while (R < Q[i].pr.second) {
      R++;
      addPrimes(R);
    }
    while (L > Q[i].pr.first) {
      L--;
      addPrimes(L);
    }
    while (R > Q[i].pr.second) {
      removePrimes(R);
      R--;
    }
    while (L < Q[i].pr.first) {
      removePrimes(L);
      L++;
    }
    answer[Q[i].id] = ans;
  }
  for (int i = (0); i <= (q - 1); ++i) printf("%d\n", answer[i]);
  return 0;
}

### Prompt

Your challenge is to write 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 int MOD = 1000000007;
const int INF = 1000000001;
const long long int LLINF = 1000000000000000001LL;
const int ROOT = 500;
const int N = 1000002;
const int NN = 200004;
int Sieve[N];
long long int Rev[N];
int Sth[N];
int RevSth[N];
void pre() {
  for (int i = (2); i <= (N - 1); ++i) Sieve[i] = i;
  for (int i = (2); i <= (N - 1); ++i)
    if (Sieve[i] == i)
      for (int j = 2 * i; j < N; j += i) Sieve[j] = min(Sieve[j], i);
  Rev[1] = 1;
  for (int i = (2); i <= (N - 1); ++i) {
    Rev[i] = -(MOD / i) * Rev[MOD % i];
    Rev[i] = (MOD + Rev[i] % MOD) % MOD;
  }
  for (int i = (1); i <= (N - 1); ++i)
    if (Sieve[i] == i) {
      Sth[i] = ((i - 1) * Rev[i]) % MOD;
      RevSth[i] = (Rev[i - 1] * i) % MOD;
    }
}
struct inter {
  pair<int, int> pr;
  int id;
};
bool comp(const inter &x, const inter &y) {
  if (x.pr.second / ROOT != y.pr.second / ROOT)
    return x.pr.second < y.pr.second;
  else {
    if ((x.pr.second / ROOT) & 1)
      return x.pr.first > y.pr.first;
    else
      return x.pr.first < y.pr.first;
  }
}
int ans = 1;
int cnt[N];
int T[NN];
vector<int> primes[NN];
void addPrimes(int i) {
  ans = ((long long int)ans * T[i]) % MOD;
  for (auto p : primes[i]) {
    if (!cnt[p]) ans = ((long long int)ans * Sth[p]) % MOD;
    cnt[p]++;
  }
}
void removePrimes(int i) {
  ans = ((long long int)ans * Rev[T[i]]) % MOD;
  for (auto p : primes[i]) {
    cnt[p]--;
    if (!cnt[p]) ans = ((long long int)ans * RevSth[p]) % MOD;
  }
}
inter Q[NN];
int answer[NN];
inline void fastRead_int(int &x) {
  register int c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
int main() {
  pre();
  int n;
  scanf("%d", &n);
  for (int i = (0); i <= (n - 1); ++i) scanf("%d", T + i);
  for (int i = (0); i <= (n - 1); ++i) {
    int x = T[i];
    primes[i].reserve(10);
    while (x > 1) {
      int p = Sieve[x];
      primes[i].push_back(p);
      while (x % p == 0) x /= p;
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = (0); i <= (q - 1); ++i) {
    fastRead_int(Q[i].pr.first);
    fastRead_int(Q[i].pr.second);
    ;
    Q[i].pr.first--;
    Q[i].pr.second--;
    Q[i].id = i;
  }
  sort(Q, Q + q, comp);
  int L = 0, R = -1;
  for (int i = (0); i <= (q - 1); ++i) {
    while (R < Q[i].pr.second) {
      R++;
      addPrimes(R);
    }
    while (L > Q[i].pr.first) {
      L--;
      addPrimes(L);
    }
    while (R > Q[i].pr.second) {
      removePrimes(R);
      R--;
    }
    while (L < Q[i].pr.first) {
      removePrimes(L);
      L++;
    }
    answer[Q[i].id] = ans;
  }
  for (int i = (0); i <= (q - 1); ++i) printf("%d\n", answer[i]);
  return 0;
}

```