#include <bits/stdc++.h>
using namespace std;
int last[1000100 + 5];
signed long long int primeBit[200010 + 5];
signed long long int productBit[200010 + 5];
signed long long int pow(signed long long int base,
                         signed long long int exponent,
                         signed long long int modulus) {
  signed long long int result = 1;
  while (exponent > 0) {
    if (exponent % 2 == 1) result = (result * base) % modulus;
    exponent = exponent >> 1;
    base = (base * base) % modulus;
  }
  return result;
}
signed long long int read(signed long long int *bit, int idx) {
  signed long long int sum = 1;
  if (idx == 0) return 1;
  while (idx > 0) {
    sum *= bit[idx];
    sum %= 1000000007;
    idx -= (idx & -idx);
  }
  return sum;
}
void update(signed long long int *bit, int idx, int val) {
  if (idx == 0) return;
  while (idx <= 200010) {
    bit[idx] *= val;
    bit[idx] %= 1000000007;
    idx += (idx & -idx);
  }
}
signed long long int rangeQuery(signed long long int *bit, int i, int j) {
  return read(bit, j) * pow(read(bit, i - 1), 1000000007 - 2, 1000000007) %
         1000000007;
}
int ans[200010 + 5], visited[1000100 + 5], A[200010 + 5];
vector<pair<int, int> > query[200010 + 5];
vector<int> factor[1000100 + 5];
void seive() {
  int S = 1000100;
  for (int i = 2; i <= S; ++i) {
    if (visited[i] == 0) {
      for (int j = i; j <= S; j += i) visited[j] = 1, factor[j].push_back(i);
    }
  }
}
int main() {
  seive();
  int now, N, Q, L, R, idx;
  fill(primeBit, primeBit + 200010, 1);
  productBit[0] = 1;
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
    productBit[i] = (productBit[i - 1] * A[i]) % 1000000007;
  }
  cin >> Q;
  for (int i = 1; i <= Q; ++i) {
    scanf("%d", &L);
    scanf("%d", &R);
    query[R].push_back(make_pair(L, i));
  }
  for (int R = 1; R <= N; ++R) {
    int x = A[R];
    for (int i = 0; i < factor[x].size(); ++i) {
      int p = factor[x][i];
      now = (p - 1) * pow(p, 1000000007 - 2, 1000000007) % 1000000007;
      update(primeBit, last[p], pow(now, 1000000007 - 2, 1000000007));
      last[p] = R;
      update(primeBit, last[p], now);
    }
    for (int j = 0; j < query[R].size(); ++j) {
      L = query[R][j].first;
      idx = query[R][j].second;
      ans[idx] = productBit[R] *
                 pow(productBit[L - 1], 1000000007 - 2, 1000000007) %
                 1000000007;
      ans[idx] = ans[idx] * rangeQuery(primeBit, L, R) % 1000000007;
    }
  }
  for (int i = 1; i <= Q; ++i) {
    printf("%d\n", ans[i]);
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
int last[1000100 + 5];
signed long long int primeBit[200010 + 5];
signed long long int productBit[200010 + 5];
signed long long int pow(signed long long int base,
                         signed long long int exponent,
                         signed long long int modulus) {
  signed long long int result = 1;
  while (exponent > 0) {
    if (exponent % 2 == 1) result = (result * base) % modulus;
    exponent = exponent >> 1;
    base = (base * base) % modulus;
  }
  return result;
}
signed long long int read(signed long long int *bit, int idx) {
  signed long long int sum = 1;
  if (idx == 0) return 1;
  while (idx > 0) {
    sum *= bit[idx];
    sum %= 1000000007;
    idx -= (idx & -idx);
  }
  return sum;
}
void update(signed long long int *bit, int idx, int val) {
  if (idx == 0) return;
  while (idx <= 200010) {
    bit[idx] *= val;
    bit[idx] %= 1000000007;
    idx += (idx & -idx);
  }
}
signed long long int rangeQuery(signed long long int *bit, int i, int j) {
  return read(bit, j) * pow(read(bit, i - 1), 1000000007 - 2, 1000000007) %
         1000000007;
}
int ans[200010 + 5], visited[1000100 + 5], A[200010 + 5];
vector<pair<int, int> > query[200010 + 5];
vector<int> factor[1000100 + 5];
void seive() {
  int S = 1000100;
  for (int i = 2; i <= S; ++i) {
    if (visited[i] == 0) {
      for (int j = i; j <= S; j += i) visited[j] = 1, factor[j].push_back(i);
    }
  }
}
int main() {
  seive();
  int now, N, Q, L, R, idx;
  fill(primeBit, primeBit + 200010, 1);
  productBit[0] = 1;
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
    productBit[i] = (productBit[i - 1] * A[i]) % 1000000007;
  }
  cin >> Q;
  for (int i = 1; i <= Q; ++i) {
    scanf("%d", &L);
    scanf("%d", &R);
    query[R].push_back(make_pair(L, i));
  }
  for (int R = 1; R <= N; ++R) {
    int x = A[R];
    for (int i = 0; i < factor[x].size(); ++i) {
      int p = factor[x][i];
      now = (p - 1) * pow(p, 1000000007 - 2, 1000000007) % 1000000007;
      update(primeBit, last[p], pow(now, 1000000007 - 2, 1000000007));
      last[p] = R;
      update(primeBit, last[p], now);
    }
    for (int j = 0; j < query[R].size(); ++j) {
      L = query[R][j].first;
      idx = query[R][j].second;
      ans[idx] = productBit[R] *
                 pow(productBit[L - 1], 1000000007 - 2, 1000000007) %
                 1000000007;
      ans[idx] = ans[idx] * rangeQuery(primeBit, L, R) % 1000000007;
    }
  }
  for (int i = 1; i <= Q; ++i) {
    printf("%d\n", ans[i]);
  }
}

```