#include <bits/stdc++.h>
using namespace std;
long long logExp(long long a, long long b) {
  if (b == 1) return a;
  long long m = logExp(a, b / 2);
  m = (m * m) % 1000000007;
  if (b % 2 == 0)
    return m;
  else
    return (m * a) % 1000000007;
}
long long mulInv(long long x) { return logExp(x, 1000000007 - 2); }
struct segtree1 {
  struct node {
    bool NULLNODE;
    long long val;
    node() { NULLNODE = false; }
  };
  node segMerge(node a, node b) {
    if (a.NULLNODE) return b;
    if (b.NULLNODE) return a;
    node ret;
    ret.val = (a.val * b.val) % 1000000007;
    return ret;
  }
  node seg[200005 * 4];
  void Update(long long idx, long long v, long long vidx, long long l,
              long long r) {
    if (vidx > r || vidx < l) {
      return;
    }
    if (l == r) {
      seg[idx].val = v;
      return;
    }
    Update(2 * idx, v, vidx, l, (l + r) / 2);
    Update(2 * idx + 1, v, vidx, (l + r) / 2 + 1, r);
    seg[idx] = segMerge(seg[2 * idx], seg[2 * idx + 1]);
  }
  node Query(long long idx, long long lq, long long rq, long long l,
             long long r) {
    if (lq > r || rq < l) {
      node dummy;
      dummy.NULLNODE = true;
      return dummy;
    }
    if (l >= lq && r <= rq) {
      return seg[idx];
    }
    node leftChild = Query(2 * idx, lq, rq, l, (l + r) / 2);
    node rightChild = Query(2 * idx + 1, lq, rq, (l + r) / 2 + 1, r);
    return segMerge(leftChild, rightChild);
  }
};
long long n, q;
long long a[200005];
long long bigprim[200005];
long long invs[1005 * 1005];
struct qq {
  long long l;
  long long r;
  long long idx;
};
qq qs[200005];
long long sols[200005];
bool cmp(qq a, qq b) { return a.r < b.r; }
long long MUL[200005];
segtree1 MULBIG;
long long last[1005];
map<long long, long long> lastBig;
bool primesIn[1005];
set<long long> primesAppeared;
long long primz[1005];
long long primit;
bool comp[1005];
void Sieve() {
  for (long long i = 2; i <= 1000; i++) {
    if (!comp[i]) {
      primz[++primit] = i;
      for (long long j = i * i; j <= 1000; j += i) comp[j] = true;
    }
  }
}
void Factorize(long long x, long long idx) {
  long long limit = sqrt(x);
  for (long long idd = 1; idd <= primit; idd++) {
    long long i = primz[idd];
    if (i > limit) break;
    if (x % i == 0) {
      if (!primesIn[i]) {
        primesIn[i] = true;
        primesAppeared.insert(i);
      }
      last[i] = idx;
      if (invs[i] == 0) invs[i] = mulInv(i);
    }
    while (x % i == 0) {
      x /= i;
    }
  }
  if (x > 1000)
    bigprim[idx] = x;
  else {
    last[x] = idx;
    if (x > 1 && !primesIn[x]) {
      primesIn[x] = true;
      primesAppeared.insert(x);
    }
  }
  if (invs[x] == 0) invs[x] = mulInv(x);
  return;
}
int main() {
  Sieve();
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  scanf("%lld", &q);
  for (long long i = 1; i <= q; i++) {
    scanf("%lld %lld", &qs[i].l, &qs[i].r);
    qs[i].idx = i;
  }
  sort(qs + 1, qs + q + 1, cmp);
  long long qit = 1;
  for (long long i = 1; i <= n; i++) {
    Factorize(a[i], i);
    if (i == 1)
      MUL[i] = a[i];
    else
      MUL[i] = (MUL[i - 1] * a[i]) % 1000000007;
    if (bigprim[i] != 0LL) {
      MULBIG.Update(1LL, ((bigprim[i] - 1LL) * invs[bigprim[i]]) % 1000000007,
                    i, 1LL, n);
      if (lastBig[bigprim[i]] > 0) {
        MULBIG.Update(1LL, 1LL, lastBig[bigprim[i]], 1LL, n);
      }
      lastBig[bigprim[i]] = i;
    } else {
      MULBIG.Update(1LL, 1LL, i, 1LL, n);
    }
    long long ret = 1;
    while (qit <= q && qs[qit].r == i) {
      long long Q1;
      if (qs[qit].l == 1)
        Q1 = MUL[qs[qit].r];
      else
        Q1 = (MUL[qs[qit].r] * mulInv(MUL[qs[qit].l - 1])) % 1000000007;
      long long Q2 = MULBIG.Query(1LL, qs[qit].l, qs[qit].r, 1LL, n).val;
      ret = (Q1 * Q2) % 1000000007;
      for (set<long long>::iterator it = primesAppeared.begin();
           it != primesAppeared.end(); ++it) {
        long long small = (*it);
        if (last[small] >= qs[qit].l) {
          ret =
              (ret * (((small - 1LL) * invs[small]) % 1000000007)) % 1000000007;
        }
      }
      sols[qs[qit].idx] = ret;
      qit++;
    }
  }
  for (long long i = 1; i <= q; i++) {
    printf("%lld\n", sols[i]);
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to 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;
long long logExp(long long a, long long b) {
  if (b == 1) return a;
  long long m = logExp(a, b / 2);
  m = (m * m) % 1000000007;
  if (b % 2 == 0)
    return m;
  else
    return (m * a) % 1000000007;
}
long long mulInv(long long x) { return logExp(x, 1000000007 - 2); }
struct segtree1 {
  struct node {
    bool NULLNODE;
    long long val;
    node() { NULLNODE = false; }
  };
  node segMerge(node a, node b) {
    if (a.NULLNODE) return b;
    if (b.NULLNODE) return a;
    node ret;
    ret.val = (a.val * b.val) % 1000000007;
    return ret;
  }
  node seg[200005 * 4];
  void Update(long long idx, long long v, long long vidx, long long l,
              long long r) {
    if (vidx > r || vidx < l) {
      return;
    }
    if (l == r) {
      seg[idx].val = v;
      return;
    }
    Update(2 * idx, v, vidx, l, (l + r) / 2);
    Update(2 * idx + 1, v, vidx, (l + r) / 2 + 1, r);
    seg[idx] = segMerge(seg[2 * idx], seg[2 * idx + 1]);
  }
  node Query(long long idx, long long lq, long long rq, long long l,
             long long r) {
    if (lq > r || rq < l) {
      node dummy;
      dummy.NULLNODE = true;
      return dummy;
    }
    if (l >= lq && r <= rq) {
      return seg[idx];
    }
    node leftChild = Query(2 * idx, lq, rq, l, (l + r) / 2);
    node rightChild = Query(2 * idx + 1, lq, rq, (l + r) / 2 + 1, r);
    return segMerge(leftChild, rightChild);
  }
};
long long n, q;
long long a[200005];
long long bigprim[200005];
long long invs[1005 * 1005];
struct qq {
  long long l;
  long long r;
  long long idx;
};
qq qs[200005];
long long sols[200005];
bool cmp(qq a, qq b) { return a.r < b.r; }
long long MUL[200005];
segtree1 MULBIG;
long long last[1005];
map<long long, long long> lastBig;
bool primesIn[1005];
set<long long> primesAppeared;
long long primz[1005];
long long primit;
bool comp[1005];
void Sieve() {
  for (long long i = 2; i <= 1000; i++) {
    if (!comp[i]) {
      primz[++primit] = i;
      for (long long j = i * i; j <= 1000; j += i) comp[j] = true;
    }
  }
}
void Factorize(long long x, long long idx) {
  long long limit = sqrt(x);
  for (long long idd = 1; idd <= primit; idd++) {
    long long i = primz[idd];
    if (i > limit) break;
    if (x % i == 0) {
      if (!primesIn[i]) {
        primesIn[i] = true;
        primesAppeared.insert(i);
      }
      last[i] = idx;
      if (invs[i] == 0) invs[i] = mulInv(i);
    }
    while (x % i == 0) {
      x /= i;
    }
  }
  if (x > 1000)
    bigprim[idx] = x;
  else {
    last[x] = idx;
    if (x > 1 && !primesIn[x]) {
      primesIn[x] = true;
      primesAppeared.insert(x);
    }
  }
  if (invs[x] == 0) invs[x] = mulInv(x);
  return;
}
int main() {
  Sieve();
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  scanf("%lld", &q);
  for (long long i = 1; i <= q; i++) {
    scanf("%lld %lld", &qs[i].l, &qs[i].r);
    qs[i].idx = i;
  }
  sort(qs + 1, qs + q + 1, cmp);
  long long qit = 1;
  for (long long i = 1; i <= n; i++) {
    Factorize(a[i], i);
    if (i == 1)
      MUL[i] = a[i];
    else
      MUL[i] = (MUL[i - 1] * a[i]) % 1000000007;
    if (bigprim[i] != 0LL) {
      MULBIG.Update(1LL, ((bigprim[i] - 1LL) * invs[bigprim[i]]) % 1000000007,
                    i, 1LL, n);
      if (lastBig[bigprim[i]] > 0) {
        MULBIG.Update(1LL, 1LL, lastBig[bigprim[i]], 1LL, n);
      }
      lastBig[bigprim[i]] = i;
    } else {
      MULBIG.Update(1LL, 1LL, i, 1LL, n);
    }
    long long ret = 1;
    while (qit <= q && qs[qit].r == i) {
      long long Q1;
      if (qs[qit].l == 1)
        Q1 = MUL[qs[qit].r];
      else
        Q1 = (MUL[qs[qit].r] * mulInv(MUL[qs[qit].l - 1])) % 1000000007;
      long long Q2 = MULBIG.Query(1LL, qs[qit].l, qs[qit].r, 1LL, n).val;
      ret = (Q1 * Q2) % 1000000007;
      for (set<long long>::iterator it = primesAppeared.begin();
           it != primesAppeared.end(); ++it) {
        long long small = (*it);
        if (last[small] >= qs[qit].l) {
          ret =
              (ret * (((small - 1LL) * invs[small]) % 1000000007)) % 1000000007;
        }
      }
      sols[qs[qit].idx] = ret;
      qit++;
    }
  }
  for (long long i = 1; i <= q; i++) {
    printf("%lld\n", sols[i]);
  }
  return 0;
}

```