#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
const int N = 1e6 + 1;
const int Mod = 1e9 + 7;
int add(int x, int y) { return (x + y) % Mod; }
int sub(int x, int y) { return (x - y + Mod) % Mod; }
int mul(int x, int y) { return (long long)x * y % Mod; }
void add_self(int& x, int y) { x = add(x, y); }
void sub_self(int& x, int y) { x = sub(x, y); }
void mul_self(int& x, int y) { x = mul(x, y); }
int fp(int x, int y) {
  if (!y) return 1;
  if (y & 1) return mul(x, fp(x, y - 1));
  return fp(mul(x, x), y >> 1);
}
int INV(int y) { return fp(y, Mod - 2); }
int INV(int x, int y) { return mul(x, INV(y)); }
int n;
int a[N];
int Pref[N];
int Suff[N];
int Cnt[N];
int inv1[N];
int inv2[N];
int inv3[N];
int Ans[N];
int Tree[N];
int Zero = 1;
vector<int> Last[N];
vector<int> Primes[N];
vector<pair<int, int> > Query[N];
int Sum(int k) {
  int Res = 1;
  for (; k >= 1; k -= k & -k) mul_self(Res, Tree[k]);
  return mul(Zero, Res);
}
void Add(int k, int x) {
  if (!k) return mul_self(Zero, x);
  for (; k <= n; k += k & -k) mul_self(Tree[k], x);
}
int main() {
  for (int i = 0; i < N; i++) Tree[i] = 1;
  for (int i = 2; i < N; i++)
    if (Primes[i].empty())
      for (int j = i; j < N; j += i) Primes[j].push_back(i);
  inv1[0] = inv1[1] = 1;
  for (long long i = 2; i < N; i++)
    inv1[i] = sub(Mod, mul(Mod / i, inv1[Mod % i]));
  for (long long i = 2; i < N; i++) inv2[i] = mul(i - 1, inv1[i]);
  for (long long i = 2; i < N; i++) inv3[i] = mul(i, inv1[i - 1]);
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  Pref[0] = 1;
  for (int i = 1; i <= n; i++) Pref[i] = mul(a[i], Pref[i - 1]);
  Suff[n + 1] = 1;
  for (int i = n; i >= 1; --i) {
    Suff[i] = Suff[i + 1];
    for (int x : Primes[a[i]])
      if (!Cnt[x]) mul_self(Suff[i], inv2[x]), Cnt[x]++;
  }
  memset(Cnt, 0, sizeof(Cnt));
  for (int i = 1; i <= n; i++) {
    Last[i].resize(Primes[a[i]].size());
    int j = 0;
    for (int x : Primes[a[i]]) {
      Last[i][j] = Cnt[x];
      Cnt[x] = i;
      j++;
    }
    debug() << " ["
            << "i"
               ": "
            << (i)
            << "] "
               " ["
            << "a[i]"
               ": "
            << (a[i])
            << "] "
               " ["
            << "Primes[a[i]]"
               ": "
            << (Primes[a[i]])
            << "] "
               " ["
            << "Last[i]"
               ": "
            << (Last[i]) << "] ";
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    Ans[i] = INV(Pref[r], Pref[l - 1]);
    Query[r].push_back(pair<int, int>(l, i));
  }
  for (int r = n; r >= 1; r--) {
    for (pair<int, int> Q : Query[r])
      mul_self(Ans[Q.second], mul(Suff[Q.first], Sum(Q.first - 1)));
    int j = 0;
    for (int x : Primes[a[r]]) Add(Last[r][j], inv3[x]), j++;
  }
  for (int i = 0; i < q; i++) printf("%d\n", Ans[i]);
}

### Prompt

Generate 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 c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
const int N = 1e6 + 1;
const int Mod = 1e9 + 7;
int add(int x, int y) { return (x + y) % Mod; }
int sub(int x, int y) { return (x - y + Mod) % Mod; }
int mul(int x, int y) { return (long long)x * y % Mod; }
void add_self(int& x, int y) { x = add(x, y); }
void sub_self(int& x, int y) { x = sub(x, y); }
void mul_self(int& x, int y) { x = mul(x, y); }
int fp(int x, int y) {
  if (!y) return 1;
  if (y & 1) return mul(x, fp(x, y - 1));
  return fp(mul(x, x), y >> 1);
}
int INV(int y) { return fp(y, Mod - 2); }
int INV(int x, int y) { return mul(x, INV(y)); }
int n;
int a[N];
int Pref[N];
int Suff[N];
int Cnt[N];
int inv1[N];
int inv2[N];
int inv3[N];
int Ans[N];
int Tree[N];
int Zero = 1;
vector<int> Last[N];
vector<int> Primes[N];
vector<pair<int, int> > Query[N];
int Sum(int k) {
  int Res = 1;
  for (; k >= 1; k -= k & -k) mul_self(Res, Tree[k]);
  return mul(Zero, Res);
}
void Add(int k, int x) {
  if (!k) return mul_self(Zero, x);
  for (; k <= n; k += k & -k) mul_self(Tree[k], x);
}
int main() {
  for (int i = 0; i < N; i++) Tree[i] = 1;
  for (int i = 2; i < N; i++)
    if (Primes[i].empty())
      for (int j = i; j < N; j += i) Primes[j].push_back(i);
  inv1[0] = inv1[1] = 1;
  for (long long i = 2; i < N; i++)
    inv1[i] = sub(Mod, mul(Mod / i, inv1[Mod % i]));
  for (long long i = 2; i < N; i++) inv2[i] = mul(i - 1, inv1[i]);
  for (long long i = 2; i < N; i++) inv3[i] = mul(i, inv1[i - 1]);
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  Pref[0] = 1;
  for (int i = 1; i <= n; i++) Pref[i] = mul(a[i], Pref[i - 1]);
  Suff[n + 1] = 1;
  for (int i = n; i >= 1; --i) {
    Suff[i] = Suff[i + 1];
    for (int x : Primes[a[i]])
      if (!Cnt[x]) mul_self(Suff[i], inv2[x]), Cnt[x]++;
  }
  memset(Cnt, 0, sizeof(Cnt));
  for (int i = 1; i <= n; i++) {
    Last[i].resize(Primes[a[i]].size());
    int j = 0;
    for (int x : Primes[a[i]]) {
      Last[i][j] = Cnt[x];
      Cnt[x] = i;
      j++;
    }
    debug() << " ["
            << "i"
               ": "
            << (i)
            << "] "
               " ["
            << "a[i]"
               ": "
            << (a[i])
            << "] "
               " ["
            << "Primes[a[i]]"
               ": "
            << (Primes[a[i]])
            << "] "
               " ["
            << "Last[i]"
               ": "
            << (Last[i]) << "] ";
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    Ans[i] = INV(Pref[r], Pref[l - 1]);
    Query[r].push_back(pair<int, int>(l, i));
  }
  for (int r = n; r >= 1; r--) {
    for (pair<int, int> Q : Query[r])
      mul_self(Ans[Q.second], mul(Suff[Q.first], Sum(Q.first - 1)));
    int j = 0;
    for (int x : Primes[a[r]]) Add(Last[r][j], inv3[x]), j++;
  }
  for (int i = 0; i < q; i++) printf("%d\n", Ans[i]);
}

```