#include <bits/stdc++.h>
using namespace std;
vector<vector<long long> > matmul(vector<vector<long long> > &a,
                                  vector<vector<long long> > &b) {
  int i, j, k, n = a.size();
  vector<vector<long long> > ans(n, vector<long long>(n));
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      long long temp = 0;
      for (k = 0; k < n; k++)
        temp = (temp + a[i][k] * b[k][j]) % (1000000007LL);
      ans[i][j] = temp;
    }
  return ans;
}
vector<vector<long long> > matpwr(vector<vector<long long> > &a, long long p) {
  int n = a.size();
  vector<vector<long long> > ans(n, vector<long long>(n));
  for (int i = 0; i < n; i++) ans[i][i] = 1;
  while (p) {
    if (p & 1) ans = matmul(ans, a);
    a = matmul(a, a);
    p >>= 1;
  }
  return ans;
}
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long invMod(long long n, long long mod = (1000000007LL)) {
  return pwr(n, mod - 2, mod);
}
int n, arr[200005], sieve[1000005];
vector<int> primes, pos[1000005], active[200004];
long long ans[1000005], sparse[19][200005], BIT[200005];
vector<pair<int, int> > queries[200005];
void update(int idx, long long val) {
  while (idx <= n) {
    BIT[idx] = (BIT[idx] * val) % (1000000007LL);
    idx += idx & (-idx);
  }
}
long long cumulativeProd(int idx) {
  long long ans = 1;
  while (idx) {
    ans = (ans * BIT[idx]) % (1000000007LL);
    idx -= idx & (-idx);
  }
  return ans;
}
long long product(int l, int r) {
  int curr = l;
  long long ans = 1;
  for (int j = 18; j >= 0; j--)
    if (curr + (1 << j) - 1 <= r) {
      ans = (ans * sparse[j][curr]) % (1000000007LL);
      curr += (1 << j);
    }
  return ans;
}
void factorize(int k) {
  int val = arr[k];
  for (int i = 0;
       i < (int)primes.size() && 1LL * primes[i] * primes[i] <= val && val != 1;
       i++)
    if (val % primes[i] == 0) {
      pos[primes[i]].push_back(k);
      while (val % primes[i] == 0) val /= primes[i];
    }
  if (val != 1) pos[val].push_back(k);
}
int main() {
  sieve[1] = 1;
  for (int i = 2; i <= 1000000; i++)
    if (!sieve[i]) {
      sieve[i] = ((i - 1) * invMod(i)) % (1000000007LL);
      primes.push_back(i);
      for (int j = 2 * i; j <= 1000000; j += i) sieve[j] = 1;
    }
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    sparse[0][i] = arr[i];
  }
  for (int i = n; i >= 1; i--) factorize(i);
  for (int j = 1; j < 19; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      sparse[j][i] = (sparse[j - 1][i] * sparse[j - 1][i + (1 << (j - 1))]) %
                     (1000000007LL);
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int lo, hi;
    scanf("%d%d", &lo, &hi);
    queries[lo].push_back(pair<int, int>(hi, i));
  }
  for (int i = 0; i <= n; i++) BIT[i] = 1;
  for (int i = 0; i < (int)primes.size(); i++)
    if (!pos[primes[i]].empty()) {
      update(pos[primes[i]].back(), sieve[primes[i]]);
      active[pos[primes[i]].back()].push_back(primes[i]);
      pos[primes[i]].pop_back();
    }
  for (int j = 1; j <= n; j++) {
    int lo = j;
    for (int k = 0; k < (int)queries[j].size(); k++) {
      int hi = queries[j][k].first, idx = queries[j][k].second;
      ans[idx] = (product(lo, hi) *
                  (cumulativeProd(hi) * invMod(cumulativeProd(lo - 1))) %
                  (1000000007LL));
      ans[idx] %= (1000000007LL);
      if (ans[idx] < 0) ans[idx] += (1000000007LL);
    }
    while (!active[j].empty()) {
      int p = active[j].back();
      active[j].pop_back();
      update(lo, invMod(sieve[p]));
      while (!pos[p].empty() && pos[p].back() <= lo) pos[p].pop_back();
      if (!pos[p].empty()) {
        update(pos[p].back(), sieve[p]);
        active[pos[p].back()].push_back(p);
        pos[p].pop_back();
      }
    }
  }
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}

### Prompt

Create a solution in CPP for 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;
vector<vector<long long> > matmul(vector<vector<long long> > &a,
                                  vector<vector<long long> > &b) {
  int i, j, k, n = a.size();
  vector<vector<long long> > ans(n, vector<long long>(n));
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      long long temp = 0;
      for (k = 0; k < n; k++)
        temp = (temp + a[i][k] * b[k][j]) % (1000000007LL);
      ans[i][j] = temp;
    }
  return ans;
}
vector<vector<long long> > matpwr(vector<vector<long long> > &a, long long p) {
  int n = a.size();
  vector<vector<long long> > ans(n, vector<long long>(n));
  for (int i = 0; i < n; i++) ans[i][i] = 1;
  while (p) {
    if (p & 1) ans = matmul(ans, a);
    a = matmul(a, a);
    p >>= 1;
  }
  return ans;
}
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long invMod(long long n, long long mod = (1000000007LL)) {
  return pwr(n, mod - 2, mod);
}
int n, arr[200005], sieve[1000005];
vector<int> primes, pos[1000005], active[200004];
long long ans[1000005], sparse[19][200005], BIT[200005];
vector<pair<int, int> > queries[200005];
void update(int idx, long long val) {
  while (idx <= n) {
    BIT[idx] = (BIT[idx] * val) % (1000000007LL);
    idx += idx & (-idx);
  }
}
long long cumulativeProd(int idx) {
  long long ans = 1;
  while (idx) {
    ans = (ans * BIT[idx]) % (1000000007LL);
    idx -= idx & (-idx);
  }
  return ans;
}
long long product(int l, int r) {
  int curr = l;
  long long ans = 1;
  for (int j = 18; j >= 0; j--)
    if (curr + (1 << j) - 1 <= r) {
      ans = (ans * sparse[j][curr]) % (1000000007LL);
      curr += (1 << j);
    }
  return ans;
}
void factorize(int k) {
  int val = arr[k];
  for (int i = 0;
       i < (int)primes.size() && 1LL * primes[i] * primes[i] <= val && val != 1;
       i++)
    if (val % primes[i] == 0) {
      pos[primes[i]].push_back(k);
      while (val % primes[i] == 0) val /= primes[i];
    }
  if (val != 1) pos[val].push_back(k);
}
int main() {
  sieve[1] = 1;
  for (int i = 2; i <= 1000000; i++)
    if (!sieve[i]) {
      sieve[i] = ((i - 1) * invMod(i)) % (1000000007LL);
      primes.push_back(i);
      for (int j = 2 * i; j <= 1000000; j += i) sieve[j] = 1;
    }
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    sparse[0][i] = arr[i];
  }
  for (int i = n; i >= 1; i--) factorize(i);
  for (int j = 1; j < 19; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      sparse[j][i] = (sparse[j - 1][i] * sparse[j - 1][i + (1 << (j - 1))]) %
                     (1000000007LL);
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int lo, hi;
    scanf("%d%d", &lo, &hi);
    queries[lo].push_back(pair<int, int>(hi, i));
  }
  for (int i = 0; i <= n; i++) BIT[i] = 1;
  for (int i = 0; i < (int)primes.size(); i++)
    if (!pos[primes[i]].empty()) {
      update(pos[primes[i]].back(), sieve[primes[i]]);
      active[pos[primes[i]].back()].push_back(primes[i]);
      pos[primes[i]].pop_back();
    }
  for (int j = 1; j <= n; j++) {
    int lo = j;
    for (int k = 0; k < (int)queries[j].size(); k++) {
      int hi = queries[j][k].first, idx = queries[j][k].second;
      ans[idx] = (product(lo, hi) *
                  (cumulativeProd(hi) * invMod(cumulativeProd(lo - 1))) %
                  (1000000007LL));
      ans[idx] %= (1000000007LL);
      if (ans[idx] < 0) ans[idx] += (1000000007LL);
    }
    while (!active[j].empty()) {
      int p = active[j].back();
      active[j].pop_back();
      update(lo, invMod(sieve[p]));
      while (!pos[p].empty() && pos[p].back() <= lo) pos[p].pop_back();
      if (!pos[p].empty()) {
        update(pos[p].back(), sieve[p]);
        active[pos[p].back()].push_back(p);
        pos[p].pop_back();
      }
    }
  }
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}

```