#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = 1000000007;
int a[N], bit[N], bitmul[N], inv[1000006], lst[1000006], l[N], res[N], n;
pair<int, int> p[N];
set<int> s[N];
void fact(int idx) {
  int x = a[idx];
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      s[idx].insert(i);
    }
  }
  if (x > 1) {
    s[idx].insert(x);
  }
}
int power(int x, int y) {
  if (y == 0) {
    return 1;
  }
  int temp = power(x, y >> 1);
  temp = ((long long)temp * temp) % M;
  if (y & 1) {
    temp = ((long long)temp * x) % M;
  }
  return temp;
}
void updmul(int x, int val) {
  while (x <= n) {
    bitmul[x] = ((long long)bitmul[x] * val) % M;
    x += x & (-x);
  }
}
int getmul(int x) {
  int mul = 1;
  while (x > 0) {
    mul = ((long long)mul * bitmul[x]) % M;
    x -= x & (-x);
  }
  return mul;
}
void upd(int x, int val) {
  while (x <= n) {
    bit[x] = ((long long)bit[x] * val) % M;
    x += x & (-x);
  }
}
int get(int x) {
  int mul = 1;
  while (x > 0) {
    mul = ((long long)mul * bit[x]) % M;
    x -= x & (-x);
  }
  return mul;
}
int main() {
  memset(inv, -1, sizeof(inv));
  memset(lst, -1, sizeof(lst));
  for (int i = 0; i < N; i++) {
    bit[i] = 1;
    bitmul[i] = 1;
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    fact(i);
    updmul(i + 1, a[i]);
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d %d", &l[i], &p[i].first);
    p[i].second = i;
  }
  sort(p, p + q);
  int j = 0;
  for (int i = 0; i < n; i++) {
    for (auto x : s[i]) {
      if (inv[x] == -1) {
        inv[x] = power(x, M - 2);
      }
      int hold = ((long long)(x - 1) * inv[x]) % M;
      if (lst[x] != -1) {
        upd(lst[x] + 1, power(hold, M - 2));
      }
      upd(i + 1, hold);
      lst[x] = i;
    }
    while (j < q && p[j].first - 1 == i) {
      res[p[j].second] =
          ((long long)get(p[j].first) * power(get(l[p[j].second] - 1), M - 2)) %
          M;
      res[p[j].second] = ((long long)res[p[j].second] *
                          (((long long)getmul(p[j].first) *
                            power(getmul(l[p[j].second] - 1), M - 2)) %
                           M)) %
                         M;
      j++;
    }
    if (j == q) {
      break;
    }
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", res[i]);
  }
  return 0;
}

### Prompt

In CPP, your task is to solve 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 N = 200005, M = 1000000007;
int a[N], bit[N], bitmul[N], inv[1000006], lst[1000006], l[N], res[N], n;
pair<int, int> p[N];
set<int> s[N];
void fact(int idx) {
  int x = a[idx];
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      s[idx].insert(i);
    }
  }
  if (x > 1) {
    s[idx].insert(x);
  }
}
int power(int x, int y) {
  if (y == 0) {
    return 1;
  }
  int temp = power(x, y >> 1);
  temp = ((long long)temp * temp) % M;
  if (y & 1) {
    temp = ((long long)temp * x) % M;
  }
  return temp;
}
void updmul(int x, int val) {
  while (x <= n) {
    bitmul[x] = ((long long)bitmul[x] * val) % M;
    x += x & (-x);
  }
}
int getmul(int x) {
  int mul = 1;
  while (x > 0) {
    mul = ((long long)mul * bitmul[x]) % M;
    x -= x & (-x);
  }
  return mul;
}
void upd(int x, int val) {
  while (x <= n) {
    bit[x] = ((long long)bit[x] * val) % M;
    x += x & (-x);
  }
}
int get(int x) {
  int mul = 1;
  while (x > 0) {
    mul = ((long long)mul * bit[x]) % M;
    x -= x & (-x);
  }
  return mul;
}
int main() {
  memset(inv, -1, sizeof(inv));
  memset(lst, -1, sizeof(lst));
  for (int i = 0; i < N; i++) {
    bit[i] = 1;
    bitmul[i] = 1;
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    fact(i);
    updmul(i + 1, a[i]);
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d %d", &l[i], &p[i].first);
    p[i].second = i;
  }
  sort(p, p + q);
  int j = 0;
  for (int i = 0; i < n; i++) {
    for (auto x : s[i]) {
      if (inv[x] == -1) {
        inv[x] = power(x, M - 2);
      }
      int hold = ((long long)(x - 1) * inv[x]) % M;
      if (lst[x] != -1) {
        upd(lst[x] + 1, power(hold, M - 2));
      }
      upd(i + 1, hold);
      lst[x] = i;
    }
    while (j < q && p[j].first - 1 == i) {
      res[p[j].second] =
          ((long long)get(p[j].first) * power(get(l[p[j].second] - 1), M - 2)) %
          M;
      res[p[j].second] = ((long long)res[p[j].second] *
                          (((long long)getmul(p[j].first) *
                            power(getmul(l[p[j].second] - 1), M - 2)) %
                           M)) %
                         M;
      j++;
    }
    if (j == q) {
      break;
    }
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", res[i]);
  }
  return 0;
}

```