#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1, x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1, x2, x3), gn(x4);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  gn(x1, x2, x3, x4), gn(x5);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T1, class T2>
inline void print(T1 x1, T2 x2) {
  printsp(x1), println(x2);
}
template <class T1, class T2, class T3>
inline void print(T1 x1, T2 x2, T3 x3) {
  printsp(x1), printsp(x2), println(x3);
}
template <class T1, class T2, class T3, class T4>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4) {
  printsp(x1), printsp(x2), printsp(x3), println(x4);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4, T5 x5) {
  printsp(x1), printsp(x2), printsp(x3), printsp(x4), println(x5);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int a[1000010];
int b[1000010];
int p[1000010];
int rev[1000010];
int pre[1000010];
int n;
int last[1000010];
int ans[1000010];
int pp[1000010];
vector<pair<int, int> > adj[1000010];
void update(int u, int val) {
  for (; u; u -= u & -u) b[u] = (long long)b[u] * val % 1000000007;
}
long long calc(int u) {
  long long ans = 1;
  for (; u <= n; u += u & -u) ans = ans * b[u] % 1000000007;
  ;
  return ans;
}
int main() {
  gn(n);
  for (int i = 1; i <= n; i++) gn(a[i]);
  int q;
  gn(q);
  for (int i = 1; i <= q; i++) {
    int l, r;
    gn(l, r);
    adj[r].push_back(pair<int, int>(l, i));
  }
  for (int i = 1; i <= n; i++) b[i] = 1;
  p[0] = 1;
  rev[0] = 1;
  for (int i = 1; i <= n; i++) p[i] = (long long)p[i - 1] * a[i] % 1000000007;
  for (int i = 1; i <= n; i++) rev[i] = power(p[i], 1000000007 - 2, 1000000007);
  pp[0] = 1;
  for (int i = 2; i < 1000010; i++)
    if (pre[i] == 0) {
      pp[i] = power(i, 1000000007 - 2, 1000000007);
      for (int j = i; j < 1000010; j += i) pre[j] = i;
    }
  for (int i = 1; i <= n; i++) {
    int first = a[i];
    while (first > 1) {
      int k = pre[first];
      if (last[k])
        update(last[k], (long long)k *
                            power((k - 1), 1000000007 - 2, 1000000007) %
                            1000000007);
      last[k] = i;
      update(i, (long long)(k - 1) * pp[k] % 1000000007);
      while (first % k == 0) first /= k;
    }
    for (int j = 0; j < adj[i].size(); j++) {
      int R = i;
      int L = adj[i][j].first;
      int id = adj[i][j].second;
      ans[id] =
          (long long)p[R] * rev[L - 1] % 1000000007 * calc(L) % 1000000007;
    }
  }
  for (int i = 1; i <= q; i++) println(ans[i]);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1, x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1, x2, x3), gn(x4);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  gn(x1, x2, x3, x4), gn(x5);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T1, class T2>
inline void print(T1 x1, T2 x2) {
  printsp(x1), println(x2);
}
template <class T1, class T2, class T3>
inline void print(T1 x1, T2 x2, T3 x3) {
  printsp(x1), printsp(x2), println(x3);
}
template <class T1, class T2, class T3, class T4>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4) {
  printsp(x1), printsp(x2), printsp(x3), println(x4);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4, T5 x5) {
  printsp(x1), printsp(x2), printsp(x3), printsp(x4), println(x5);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int a[1000010];
int b[1000010];
int p[1000010];
int rev[1000010];
int pre[1000010];
int n;
int last[1000010];
int ans[1000010];
int pp[1000010];
vector<pair<int, int> > adj[1000010];
void update(int u, int val) {
  for (; u; u -= u & -u) b[u] = (long long)b[u] * val % 1000000007;
}
long long calc(int u) {
  long long ans = 1;
  for (; u <= n; u += u & -u) ans = ans * b[u] % 1000000007;
  ;
  return ans;
}
int main() {
  gn(n);
  for (int i = 1; i <= n; i++) gn(a[i]);
  int q;
  gn(q);
  for (int i = 1; i <= q; i++) {
    int l, r;
    gn(l, r);
    adj[r].push_back(pair<int, int>(l, i));
  }
  for (int i = 1; i <= n; i++) b[i] = 1;
  p[0] = 1;
  rev[0] = 1;
  for (int i = 1; i <= n; i++) p[i] = (long long)p[i - 1] * a[i] % 1000000007;
  for (int i = 1; i <= n; i++) rev[i] = power(p[i], 1000000007 - 2, 1000000007);
  pp[0] = 1;
  for (int i = 2; i < 1000010; i++)
    if (pre[i] == 0) {
      pp[i] = power(i, 1000000007 - 2, 1000000007);
      for (int j = i; j < 1000010; j += i) pre[j] = i;
    }
  for (int i = 1; i <= n; i++) {
    int first = a[i];
    while (first > 1) {
      int k = pre[first];
      if (last[k])
        update(last[k], (long long)k *
                            power((k - 1), 1000000007 - 2, 1000000007) %
                            1000000007);
      last[k] = i;
      update(i, (long long)(k - 1) * pp[k] % 1000000007);
      while (first % k == 0) first /= k;
    }
    for (int j = 0; j < adj[i].size(); j++) {
      int R = i;
      int L = adj[i][j].first;
      int id = adj[i][j].second;
      ans[id] =
          (long long)p[R] * rev[L - 1] % 1000000007 * calc(L) % 1000000007;
    }
  }
  for (int i = 1; i <= q; i++) println(ans[i]);
  return 0;
}

```