#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet {
char _c;
long long I() {
  long long x = 0;
  long long f = 1;
  while (_c < '0' or _c > '9') f = (_c == '-') ? -1 : 1, _c = getchar();
  while (_c >= '0' and _c <= '9')
    x = (x << 1) + (x << 3) + (_c ^ 48), _c = getchar();
  return (x = (f == 1) ? x : -x);
}
void Rd(long long cnt, ...) {
  va_list args;
  va_start(args, cnt);
  for (long long i = 1; i <= cnt; ++i) {
    long long* x = va_arg(args, long long*);
    (*x) = I();
  }
  va_end(args);
}
void mul(long long& a, long long b) { a = (a * b) % 1000000007; }
long long qpow(long long a, long long b, long long m) {
  long long r = 1;
  while (b) {
    if (b & 1) mul(r, a);
    mul(a, a), b >>= 1;
  }
  return r;
}
long long inv(long long x) { return qpow(x, 1000000007 - 2, 1000000007); }
class BIT {
 public:
  long long tree[1666666], len;
  void Build(long long _len) {
    memset(tree, 0, sizeof(tree));
    len = _len;
    for (long long i = 1; i <= len; ++i) tree[i] = 1;
  }
  void Add(long long pos, long long x) {
    while (pos <= len) mul(tree[pos], x), pos += (pos & (-pos));
  }
  long long Query(long long pos) {
    long long ans = 1;
    while (pos > 0) mul(ans, tree[pos]), pos -= (pos & (-pos));
    return ans;
  }
  long long RQuery(long long l, long long r) {
    return Query(r) * inv(Query(l - 1)) % 1000000007;
  }
} T;
struct node {
  long long l, r, id;
} q[1666666];
bool operator<(node a, node b) { return a.r < b.r; }
long long n, m, a[1666666];
void Input() {
  n = I();
  for (long long i = 1; i <= n; ++i) a[i] = I();
  m = I();
  for (long long i = 1; i <= m; ++i) q[i] = (node){I(), I(), i};
  sort(q + 1, q + m + 1);
}
long long s[1666666];
bool vis[1666666];
vector<long long> fac[1666666];
long long last[1666666];
long long ans[1666666];
void Soviet() {
  s[0] = 1;
  for (long long i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % 1000000007;
  for (long long i = 2; i <= 1e6; ++i)
    if (!vis[i])
      for (long long j = i; j <= 1e6; j += i) fac[j].push_back(i), vis[j] = 1;
  T.Build(1e6);
  long long pos = 1;
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 0; j <= ((long long)fac[a[i]].size()) - 1; ++j) {
      long long u = fac[a[i]][j];
      if (last[u]) T.Add(last[u], inv(inv(u) * (u - 1) % 1000000007));
      T.Add(i, inv(u) * (u - 1) % 1000000007);
      last[u] = i;
    }
    while (pos <= m and q[pos].r == i) {
      long long l = q[pos].l, r = q[pos].r;
      ans[q[pos].id] =
          (s[r] * inv(s[l - 1])) % 1000000007 * T.RQuery(l, r) % 1000000007;
      ++pos;
    }
  }
  for (long long i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
void IsMyWife() {
  Input();
  Soviet();
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  getchar();
  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;
namespace Flandre_Scarlet {
char _c;
long long I() {
  long long x = 0;
  long long f = 1;
  while (_c < '0' or _c > '9') f = (_c == '-') ? -1 : 1, _c = getchar();
  while (_c >= '0' and _c <= '9')
    x = (x << 1) + (x << 3) + (_c ^ 48), _c = getchar();
  return (x = (f == 1) ? x : -x);
}
void Rd(long long cnt, ...) {
  va_list args;
  va_start(args, cnt);
  for (long long i = 1; i <= cnt; ++i) {
    long long* x = va_arg(args, long long*);
    (*x) = I();
  }
  va_end(args);
}
void mul(long long& a, long long b) { a = (a * b) % 1000000007; }
long long qpow(long long a, long long b, long long m) {
  long long r = 1;
  while (b) {
    if (b & 1) mul(r, a);
    mul(a, a), b >>= 1;
  }
  return r;
}
long long inv(long long x) { return qpow(x, 1000000007 - 2, 1000000007); }
class BIT {
 public:
  long long tree[1666666], len;
  void Build(long long _len) {
    memset(tree, 0, sizeof(tree));
    len = _len;
    for (long long i = 1; i <= len; ++i) tree[i] = 1;
  }
  void Add(long long pos, long long x) {
    while (pos <= len) mul(tree[pos], x), pos += (pos & (-pos));
  }
  long long Query(long long pos) {
    long long ans = 1;
    while (pos > 0) mul(ans, tree[pos]), pos -= (pos & (-pos));
    return ans;
  }
  long long RQuery(long long l, long long r) {
    return Query(r) * inv(Query(l - 1)) % 1000000007;
  }
} T;
struct node {
  long long l, r, id;
} q[1666666];
bool operator<(node a, node b) { return a.r < b.r; }
long long n, m, a[1666666];
void Input() {
  n = I();
  for (long long i = 1; i <= n; ++i) a[i] = I();
  m = I();
  for (long long i = 1; i <= m; ++i) q[i] = (node){I(), I(), i};
  sort(q + 1, q + m + 1);
}
long long s[1666666];
bool vis[1666666];
vector<long long> fac[1666666];
long long last[1666666];
long long ans[1666666];
void Soviet() {
  s[0] = 1;
  for (long long i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % 1000000007;
  for (long long i = 2; i <= 1e6; ++i)
    if (!vis[i])
      for (long long j = i; j <= 1e6; j += i) fac[j].push_back(i), vis[j] = 1;
  T.Build(1e6);
  long long pos = 1;
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 0; j <= ((long long)fac[a[i]].size()) - 1; ++j) {
      long long u = fac[a[i]][j];
      if (last[u]) T.Add(last[u], inv(inv(u) * (u - 1) % 1000000007));
      T.Add(i, inv(u) * (u - 1) % 1000000007);
      last[u] = i;
    }
    while (pos <= m and q[pos].r == i) {
      long long l = q[pos].l, r = q[pos].r;
      ans[q[pos].id] =
          (s[r] * inv(s[l - 1])) % 1000000007 * T.RQuery(l, r) % 1000000007;
      ++pos;
    }
  }
  for (long long i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
void IsMyWife() {
  Input();
  Soviet();
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  getchar();
  return 0;
}

```