#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void amin(T &a, const T &b) {
  if (b < a) a = b;
}
template <class T>
inline void amax(T &a, const T &b) {
  if (a < b) a = b;
}
template <class T>
struct Fenwick : vector<T> {
  int N;
  Fenwick(int N_ = 0) : vector<T>(N_, 1), N(N_) {}
  void add(int i, T x) {
    for (; i < N; i |= i + 1) vector<T>::operator[](i) *= x;
  }
  T sum(int r) {
    T s = 1;
    for (; r; r &= r - 1) s *= vector<T>::operator[](r - 1);
    return s;
  }
};
template <int MOD>
struct ModInt {
  unsigned x;
  void undef() { x = -1; }
  bool isnan() const { return x == -1; }
  inline int getInt() const { return (int)x; }
  template <class T>
  T get() const {
    return (T)x;
  }
  inline int mod() const { return MOD; }
  ModInt(int y = 0) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(long long y) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned long long y) {
    if (MOD <= y)
      x = y % MOD;
    else
      x = y;
  }
  ModInt &operator+=(const ModInt &y) {
    if ((x += y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt &y) {
    if ((x += MOD - y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt &y) {
    x = (unsigned long long)x * y.x % MOD;
    return *this;
  }
  ModInt &operator/=(const ModInt &y) {
    x = (unsigned long long)x * y.inv().x % MOD;
    return *this;
  }
  ModInt operator-() const { return (x ? MOD - x : 0); }
  ModInt inv() const {
    int a = MOD, b = x, u = 0, v = 1;
    while (b) {
      int t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if (u < 0) u += MOD;
    return ModInt(u);
  }
  ModInt pow(long long y) const {
    ModInt b = *this, r = 1;
    if (y < 0) {
      b = b.inv();
      y = -y;
    }
    for (; y; y >>= 1) {
      if (y & 1) r *= b;
      b *= b;
    }
    return r;
  }
};
const long long MOD = 1000000007;
ModInt<MOD> operator+(ModInt<MOD> x, const ModInt<MOD> &y) {
  if ((x.x += y.x) >= (unsigned)x.mod()) x.x -= x.mod();
  return x;
}
ModInt<MOD> operator-(ModInt<MOD> x, const ModInt<MOD> &y) {
  if ((x.x += x.mod() - y.x) >= (unsigned)x.mod()) x.x -= x.mod();
  return x;
}
ModInt<MOD> operator*(ModInt<MOD> x, const ModInt<MOD> &y) {
  x.x = (unsigned long long)x.x * y.x % x.mod();
  return x;
}
ModInt<MOD> operator/(ModInt<MOD> x, const ModInt<MOD> &y) {
  x.x = (unsigned long long)x.x * y.inv().x % x.mod();
  return x;
}
bool operator<(const ModInt<MOD> &x, const ModInt<MOD> &y) { return x.x < y.x; }
bool operator==(const ModInt<MOD> &x, const ModInt<MOD> &y) {
  return x.x == y.x;
}
bool operator!=(const ModInt<MOD> &x, const ModInt<MOD> &y) {
  return x.x != y.x;
}
const int MAX = 1000100;
long long inv[MAX + 1], fact[MAX + 1], fact_inv[MAX + 1];
void init() {
  inv[1] = 1;
  for (int i = 2; i <= MAX; i++) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
  fact[0] = fact_inv[0] = 1;
  for (int i = 1; i <= MAX; i++) {
    fact[i] = fact[i - 1] * i % MOD;
    fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
  }
}
int min_factor[MAX + 1];
vector<int> prime;
void make_prime() {
  for (int i = 2; i <= MAX; i += 2) min_factor[i] = 2;
  for (int i = 3; i <= MAX; i += 3)
    if (!min_factor[i]) min_factor[i] = 3;
  for (int i = 5, d = 2; i * i <= MAX;) {
    if (!min_factor[i]) {
      min_factor[i] = i;
      for (int j = i * i; j <= MAX; j += i)
        if (!min_factor[j]) min_factor[j] = i;
    }
    i += d;
    d = 6 - d;
  }
  for (int i = 2; i <= MAX; i++) {
    if (min_factor[i] == 0) min_factor[i] = i;
    if (min_factor[i] == i) prime.push_back(i);
  }
}
map<long long, int> fast_prime_factor(int n) {
  map<long long, int> r;
  while (n > 1) {
    int t = min_factor[n], cnt = 0;
    while (n % t == 0) {
      n /= t, cnt++;
    }
    r[t] = cnt;
  }
  return r;
}
int N;
int A[200111];
int Q;
struct Data {
  int l, r, i;
  bool operator<(const Data &y) const { return r < y.r; }
} D[200111];
int last[MAX];
int ans[200111];
int main() {
  init();
  make_prime();
  scanf("%d", &N);
  for (int i = 0, i_len = (N); i < i_len; ++i) scanf("%d", A + i);
  scanf("%d", &Q);
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    scanf("%d%d", &D[i].l, &D[i].r);
    D[i].l--;
    D[i].i = i;
  }
  for (int i = 0, i_len = (MAX); i < i_len; ++i) last[i] = N;
  sort(D, D + Q);
  Fenwick<ModInt<MOD> > F(N + 10);
  for (int i = 0, j = 0; i < Q; i++) {
    while (j < D[i].r) {
      map<long long, int> g = fast_prime_factor(A[j]);
      for (__typeof((g).begin()) e = (g).begin(), e_end = (g).end(); e != e_end;
           ++e) {
        int pr = e->first;
        int pos = last[pr];
        F.add(pos, ModInt<MOD>(inv[pr - 1]) * pr);
        F.add(j, ModInt<MOD>(pr - 1) * ModInt<MOD>(pr).pow(e->second - 1));
        last[pr] = j;
      }
      j++;
    }
    ModInt<MOD> l = F.sum(D[i].l), r = F.sum(D[i].r);
    r *= l.inv();
    ans[D[i].i] = r.getInt();
  }
  for (int i = 0, i_len = (Q); i < i_len; ++i) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Your task is to create 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;
template <class T>
inline void amin(T &a, const T &b) {
  if (b < a) a = b;
}
template <class T>
inline void amax(T &a, const T &b) {
  if (a < b) a = b;
}
template <class T>
struct Fenwick : vector<T> {
  int N;
  Fenwick(int N_ = 0) : vector<T>(N_, 1), N(N_) {}
  void add(int i, T x) {
    for (; i < N; i |= i + 1) vector<T>::operator[](i) *= x;
  }
  T sum(int r) {
    T s = 1;
    for (; r; r &= r - 1) s *= vector<T>::operator[](r - 1);
    return s;
  }
};
template <int MOD>
struct ModInt {
  unsigned x;
  void undef() { x = -1; }
  bool isnan() const { return x == -1; }
  inline int getInt() const { return (int)x; }
  template <class T>
  T get() const {
    return (T)x;
  }
  inline int mod() const { return MOD; }
  ModInt(int y = 0) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(long long y) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned long long y) {
    if (MOD <= y)
      x = y % MOD;
    else
      x = y;
  }
  ModInt &operator+=(const ModInt &y) {
    if ((x += y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt &y) {
    if ((x += MOD - y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt &y) {
    x = (unsigned long long)x * y.x % MOD;
    return *this;
  }
  ModInt &operator/=(const ModInt &y) {
    x = (unsigned long long)x * y.inv().x % MOD;
    return *this;
  }
  ModInt operator-() const { return (x ? MOD - x : 0); }
  ModInt inv() const {
    int a = MOD, b = x, u = 0, v = 1;
    while (b) {
      int t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if (u < 0) u += MOD;
    return ModInt(u);
  }
  ModInt pow(long long y) const {
    ModInt b = *this, r = 1;
    if (y < 0) {
      b = b.inv();
      y = -y;
    }
    for (; y; y >>= 1) {
      if (y & 1) r *= b;
      b *= b;
    }
    return r;
  }
};
const long long MOD = 1000000007;
ModInt<MOD> operator+(ModInt<MOD> x, const ModInt<MOD> &y) {
  if ((x.x += y.x) >= (unsigned)x.mod()) x.x -= x.mod();
  return x;
}
ModInt<MOD> operator-(ModInt<MOD> x, const ModInt<MOD> &y) {
  if ((x.x += x.mod() - y.x) >= (unsigned)x.mod()) x.x -= x.mod();
  return x;
}
ModInt<MOD> operator*(ModInt<MOD> x, const ModInt<MOD> &y) {
  x.x = (unsigned long long)x.x * y.x % x.mod();
  return x;
}
ModInt<MOD> operator/(ModInt<MOD> x, const ModInt<MOD> &y) {
  x.x = (unsigned long long)x.x * y.inv().x % x.mod();
  return x;
}
bool operator<(const ModInt<MOD> &x, const ModInt<MOD> &y) { return x.x < y.x; }
bool operator==(const ModInt<MOD> &x, const ModInt<MOD> &y) {
  return x.x == y.x;
}
bool operator!=(const ModInt<MOD> &x, const ModInt<MOD> &y) {
  return x.x != y.x;
}
const int MAX = 1000100;
long long inv[MAX + 1], fact[MAX + 1], fact_inv[MAX + 1];
void init() {
  inv[1] = 1;
  for (int i = 2; i <= MAX; i++) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
  fact[0] = fact_inv[0] = 1;
  for (int i = 1; i <= MAX; i++) {
    fact[i] = fact[i - 1] * i % MOD;
    fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
  }
}
int min_factor[MAX + 1];
vector<int> prime;
void make_prime() {
  for (int i = 2; i <= MAX; i += 2) min_factor[i] = 2;
  for (int i = 3; i <= MAX; i += 3)
    if (!min_factor[i]) min_factor[i] = 3;
  for (int i = 5, d = 2; i * i <= MAX;) {
    if (!min_factor[i]) {
      min_factor[i] = i;
      for (int j = i * i; j <= MAX; j += i)
        if (!min_factor[j]) min_factor[j] = i;
    }
    i += d;
    d = 6 - d;
  }
  for (int i = 2; i <= MAX; i++) {
    if (min_factor[i] == 0) min_factor[i] = i;
    if (min_factor[i] == i) prime.push_back(i);
  }
}
map<long long, int> fast_prime_factor(int n) {
  map<long long, int> r;
  while (n > 1) {
    int t = min_factor[n], cnt = 0;
    while (n % t == 0) {
      n /= t, cnt++;
    }
    r[t] = cnt;
  }
  return r;
}
int N;
int A[200111];
int Q;
struct Data {
  int l, r, i;
  bool operator<(const Data &y) const { return r < y.r; }
} D[200111];
int last[MAX];
int ans[200111];
int main() {
  init();
  make_prime();
  scanf("%d", &N);
  for (int i = 0, i_len = (N); i < i_len; ++i) scanf("%d", A + i);
  scanf("%d", &Q);
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    scanf("%d%d", &D[i].l, &D[i].r);
    D[i].l--;
    D[i].i = i;
  }
  for (int i = 0, i_len = (MAX); i < i_len; ++i) last[i] = N;
  sort(D, D + Q);
  Fenwick<ModInt<MOD> > F(N + 10);
  for (int i = 0, j = 0; i < Q; i++) {
    while (j < D[i].r) {
      map<long long, int> g = fast_prime_factor(A[j]);
      for (__typeof((g).begin()) e = (g).begin(), e_end = (g).end(); e != e_end;
           ++e) {
        int pr = e->first;
        int pos = last[pr];
        F.add(pos, ModInt<MOD>(inv[pr - 1]) * pr);
        F.add(j, ModInt<MOD>(pr - 1) * ModInt<MOD>(pr).pow(e->second - 1));
        last[pr] = j;
      }
      j++;
    }
    ModInt<MOD> l = F.sum(D[i].l), r = F.sum(D[i].r);
    r *= l.inv();
    ans[D[i].i] = r.getInt();
  }
  for (int i = 0, i_len = (Q); i < i_len; ++i) printf("%d\n", ans[i]);
  return 0;
}

```