#include <bits/stdc++.h>
using namespace std;
long long int powm(long long int a, int b, int n) {
  long long int rm = 1;
  while (b) {
    if (b % 2) {
      rm = (rm * a) % n;
    }
    a = (a * a) % n;
    b /= 2;
  }
  return rm;
}
const int N = 200009;
int inv[N], npr = 0, pr[1010];
int prv_hash[1000009] = {0}, l[N], r[N];
long long int dp[N], seg[N * 4 + 1000], Ans[N], a[N];
vector<pair<int, int> > v;
vector<int> edge[N], ledge[N];
void update(int n, int it, int f, int q1, int q2, long long int val) {
  if (it == q1 && f == q2) {
    seg[n] = (seg[n] * val) % int(1e9 + 7);
    return;
  }
  int m = (it + f) / 2;
  if (q2 <= m)
    update(n * 2, it, m, q1, q2, val);
  else if (q1 > m)
    update(n * 2 + 1, m + 1, f, q1, q2, val);
  else {
    update(n * 2, it, m, q1, m, val);
    update(n * 2 + 1, m + 1, f, m + 1, q2, val);
  }
}
long long int query(int n, int it, int f, int q, long long int prv) {
  prv = (prv * seg[n]) % int(1e9 + 7);
  if (it == f) return prv;
  int m = (it + f) / 2;
  if (q <= m)
    return query(n * 2, it, m, q, prv);
  else
    return query(n * 2 + 1, m + 1, f, q, prv);
}
void sieve() {
  for (int i = 2; i <= 1000; ++i) {
    pr[++npr] = i;
    for (int j = sqrt(i); j >= 2; j--) {
      if (i % j == 0) {
        --npr;
        break;
      }
    }
  }
}
int main() {
  int n, Q, q;
  sieve();
  cin >> n;
  dp[0] = 1;
  for (int i = int(1); i <= (int)n; i++) {
    scanf("%d", &q);
    ;
    a[i] = q;
    dp[i] = (dp[i - 1] * a[i]) % int(1e9 + 7);
  }
  cin >> Q;
  v.push_back(make_pair(0, 0));
  for (int i = int(1); i <= (int)Q; i++) {
    cin >> l[i] >> r[i];
    v.push_back(make_pair(l[i], i));
    edge[r[i]].push_back(i);
  }
  sort(v.begin() + 1, v.end());
  int p = 1;
  for (int i = int(1); i <= (int)Q; i++) inv[v[i].second] = i;
  for (int i = 1; i <= 4 * N; ++i) seg[i] = 1;
  for (int i = 1; i <= n; ++i) {
    while (p < Q) {
      if (v[p + 1].first > i) break;
      ++p;
    }
    for (int j = 1; j <= npr; ++j) {
      if (a[i] % pr[j] == 0) {
        while (a[i] % pr[j] == 0) a[i] /= pr[j];
        if (v[p].first <= i && prv_hash[pr[j]] < p) {
          update(1, 1, Q, prv_hash[pr[j]] + 1, p,
                 (1ll * (pr[j] - 1) *
                  powm(pr[j], int(1e9 + 7) - 2, int(1e9 + 7))) %
                     int(1e9 + 7));
        }
        if (v[p].first <= i) prv_hash[pr[j]] = p;
      }
    }
    if (a[i] > 1) {
      if (v[p].first <= i && prv_hash[a[i]] < p) {
        update(1, 1, Q, prv_hash[a[i]] + 1, p,
               (1ll * (a[i] - 1) * powm(a[i], int(1e9 + 7) - 2, int(1e9 + 7))) %
                   int(1e9 + 7));
      }
      if (v[p].first <= i) prv_hash[a[i]] = p;
    }
    for (int j = 0; j < edge[i].size(); ++j) {
      int qn = edge[i][j];
      int ans = query(1, 1, Q, inv[qn], 1);
      Ans[qn] = ans;
    }
  }
  for (int i = int(1); i <= (int)Q; i++) {
    Ans[i] *= dp[r[i]];
    Ans[i] %= int(1e9 + 7);
    Ans[i] *= powm(dp[l[i] - 1], int(1e9 + 7) - 2, int(1e9 + 7));
    Ans[i] %= int(1e9 + 7);
    cout << Ans[i] << endl;
  }
  return 0;
}

### 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;
long long int powm(long long int a, int b, int n) {
  long long int rm = 1;
  while (b) {
    if (b % 2) {
      rm = (rm * a) % n;
    }
    a = (a * a) % n;
    b /= 2;
  }
  return rm;
}
const int N = 200009;
int inv[N], npr = 0, pr[1010];
int prv_hash[1000009] = {0}, l[N], r[N];
long long int dp[N], seg[N * 4 + 1000], Ans[N], a[N];
vector<pair<int, int> > v;
vector<int> edge[N], ledge[N];
void update(int n, int it, int f, int q1, int q2, long long int val) {
  if (it == q1 && f == q2) {
    seg[n] = (seg[n] * val) % int(1e9 + 7);
    return;
  }
  int m = (it + f) / 2;
  if (q2 <= m)
    update(n * 2, it, m, q1, q2, val);
  else if (q1 > m)
    update(n * 2 + 1, m + 1, f, q1, q2, val);
  else {
    update(n * 2, it, m, q1, m, val);
    update(n * 2 + 1, m + 1, f, m + 1, q2, val);
  }
}
long long int query(int n, int it, int f, int q, long long int prv) {
  prv = (prv * seg[n]) % int(1e9 + 7);
  if (it == f) return prv;
  int m = (it + f) / 2;
  if (q <= m)
    return query(n * 2, it, m, q, prv);
  else
    return query(n * 2 + 1, m + 1, f, q, prv);
}
void sieve() {
  for (int i = 2; i <= 1000; ++i) {
    pr[++npr] = i;
    for (int j = sqrt(i); j >= 2; j--) {
      if (i % j == 0) {
        --npr;
        break;
      }
    }
  }
}
int main() {
  int n, Q, q;
  sieve();
  cin >> n;
  dp[0] = 1;
  for (int i = int(1); i <= (int)n; i++) {
    scanf("%d", &q);
    ;
    a[i] = q;
    dp[i] = (dp[i - 1] * a[i]) % int(1e9 + 7);
  }
  cin >> Q;
  v.push_back(make_pair(0, 0));
  for (int i = int(1); i <= (int)Q; i++) {
    cin >> l[i] >> r[i];
    v.push_back(make_pair(l[i], i));
    edge[r[i]].push_back(i);
  }
  sort(v.begin() + 1, v.end());
  int p = 1;
  for (int i = int(1); i <= (int)Q; i++) inv[v[i].second] = i;
  for (int i = 1; i <= 4 * N; ++i) seg[i] = 1;
  for (int i = 1; i <= n; ++i) {
    while (p < Q) {
      if (v[p + 1].first > i) break;
      ++p;
    }
    for (int j = 1; j <= npr; ++j) {
      if (a[i] % pr[j] == 0) {
        while (a[i] % pr[j] == 0) a[i] /= pr[j];
        if (v[p].first <= i && prv_hash[pr[j]] < p) {
          update(1, 1, Q, prv_hash[pr[j]] + 1, p,
                 (1ll * (pr[j] - 1) *
                  powm(pr[j], int(1e9 + 7) - 2, int(1e9 + 7))) %
                     int(1e9 + 7));
        }
        if (v[p].first <= i) prv_hash[pr[j]] = p;
      }
    }
    if (a[i] > 1) {
      if (v[p].first <= i && prv_hash[a[i]] < p) {
        update(1, 1, Q, prv_hash[a[i]] + 1, p,
               (1ll * (a[i] - 1) * powm(a[i], int(1e9 + 7) - 2, int(1e9 + 7))) %
                   int(1e9 + 7));
      }
      if (v[p].first <= i) prv_hash[a[i]] = p;
    }
    for (int j = 0; j < edge[i].size(); ++j) {
      int qn = edge[i][j];
      int ans = query(1, 1, Q, inv[qn], 1);
      Ans[qn] = ans;
    }
  }
  for (int i = int(1); i <= (int)Q; i++) {
    Ans[i] *= dp[r[i]];
    Ans[i] %= int(1e9 + 7);
    Ans[i] *= powm(dp[l[i] - 1], int(1e9 + 7) - 2, int(1e9 + 7));
    Ans[i] %= int(1e9 + 7);
    cout << Ans[i] << endl;
  }
  return 0;
}

```