#include <bits/stdc++.h>
using namespace std;
void Read(long long &val) {
  val = 0;
  char c;
  do {
    c = getchar();
  } while (!isdigit(c));
  while (isdigit(c)) {
    val = val * 10 + c - '0';
    c = getchar();
  }
}
void Write(long long val) {
  if (val < 0)
    putchar('-'), Write(-val);
  else if (val < 10)
    putchar('0' + val);
  else
    Write(val / 10), putchar('0' + val % 10);
}
struct ii {
  long long r, id;
  ii(){};
  ii(long long r, long long id) : r(r), id(id){};
};
const long long N = 2e5 + 4, VAL = 1e6 + 4, MOD = 1e9 + 7;
long long n, Q, a[N];
vector<ii> ques[N];
bool isPrime[VAL];
long long Div[VAL];
void sieve() {
  memset(isPrime, true, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for (long long i = 2; i < VAL; ++i) {
    if (!isPrime[i]) continue;
    long long j = 2 * i;
    Div[i] = i;
    while (j < VAL) {
      isPrime[j] = false;
      Div[j] = i;
      j += i;
    }
  }
}
bool vis[VAL];
vector<long long> lsPrime, Pos[VAL];
void prepare() {
  for (long long i = 1; i <= n; ++i) {
    long long val = a[i];
    while (val > 1) {
      long long prime = Div[val];
      while (val % prime == 0) val /= prime;
      Pos[prime].push_back(i);
      if (!vis[prime]) {
        vis[prime] = true;
        lsPrime.push_back(prime);
      }
    }
  }
  for (long long prime : lsPrime) {
    Pos[prime].push_back(n + 1);
    reverse(Pos[prime].begin(), Pos[prime].end());
    vis[prime] = false;
  }
}
long long Pow(long long a, long long b) {
  long long ans = 1;
  for (; b > 0; b /= 2, a = (a * a) % MOD)
    if (b % 2 == 1) ans = (ans * a) % MOD;
  return ans;
}
long long ans[N], rez[N];
struct Binary_Indexed_Tree {
  long long node[N];
  Binary_Indexed_Tree() {
    for (long long i = 0; i < N; ++i) node[i] = 1;
  }
  void update(long long pos, long long val) {
    for (long long i = pos; i <= n; i += i & (-i))
      node[i] = (node[i] * val) % MOD;
  }
  long long get(long long pos) {
    long long ans = 1;
    for (long long i = pos; i > 0; i -= i & (-i)) ans = (ans * node[i]) % MOD;
    return ans;
  }
} BIT;
void update(long long l, long long r, long long val) {
  if (l > r) return;
  long long inv = Pow(val, MOD - 2);
  BIT.update(l, val);
  BIT.update(r + 1, inv);
}
long long Mul[VAL], invMul[VAL], Product[N];
void sol() {
  sieve();
  prepare();
  for (long long prime : lsPrime) {
    Mul[prime] = (prime - 1) * Pow(prime, MOD - 2) % MOD;
    invMul[prime] = Pow(Mul[prime], MOD - 2);
  }
  for (long long i = 1; i <= n; ++i) {
    long long val = a[i];
    update(i, i, (i == 1) ? 1 : BIT.get(i - 1));
    while (val > 1) {
      long long prime = Div[val];
      while (val % prime == 0) val /= prime;
      if (vis[prime]) continue;
      vis[prime] = true;
      update(i, i, Mul[prime]);
    }
  }
  for (ii foo : ques[1]) rez[foo.id] = BIT.get(foo.r);
  for (long long i = 2; i <= n; ++i) {
    long long val = a[i - 1];
    while (val > 1) {
      long long prime = Div[val];
      while (val % prime == 0) val /= prime;
      Pos[prime].pop_back();
      update(i, Pos[prime].back() - 1, invMul[prime]);
    }
    for (ii foo : ques[i]) rez[foo.id] = BIT.get(foo.r);
  }
  Product[0] = 1;
  for (long long i = 1; i <= n; ++i) Product[i] = (Product[i - 1] * a[i]) % MOD;
  for (long long l = 1; l <= n; ++l)
    for (ii foo : ques[l]) {
      rez[foo.id] = rez[foo.id] * Product[foo.r] % MOD *
                    Pow(Product[l - 1], MOD - 2) % MOD;
    }
  for (long long i = 1; i <= Q; ++i) {
    Write(rez[i]), putchar('\n');
  }
}
int main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
  }
  Read(n);
  for (long long i = 1; i <= n; ++i) Read(a[i]);
  Read(Q);
  long long l, r;
  for (long long i = 1; i <= Q; ++i) {
    Read(l);
    Read(r);
    ques[l].push_back(ii(r, i));
  }
  sol();
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
void Read(long long &val) {
  val = 0;
  char c;
  do {
    c = getchar();
  } while (!isdigit(c));
  while (isdigit(c)) {
    val = val * 10 + c - '0';
    c = getchar();
  }
}
void Write(long long val) {
  if (val < 0)
    putchar('-'), Write(-val);
  else if (val < 10)
    putchar('0' + val);
  else
    Write(val / 10), putchar('0' + val % 10);
}
struct ii {
  long long r, id;
  ii(){};
  ii(long long r, long long id) : r(r), id(id){};
};
const long long N = 2e5 + 4, VAL = 1e6 + 4, MOD = 1e9 + 7;
long long n, Q, a[N];
vector<ii> ques[N];
bool isPrime[VAL];
long long Div[VAL];
void sieve() {
  memset(isPrime, true, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for (long long i = 2; i < VAL; ++i) {
    if (!isPrime[i]) continue;
    long long j = 2 * i;
    Div[i] = i;
    while (j < VAL) {
      isPrime[j] = false;
      Div[j] = i;
      j += i;
    }
  }
}
bool vis[VAL];
vector<long long> lsPrime, Pos[VAL];
void prepare() {
  for (long long i = 1; i <= n; ++i) {
    long long val = a[i];
    while (val > 1) {
      long long prime = Div[val];
      while (val % prime == 0) val /= prime;
      Pos[prime].push_back(i);
      if (!vis[prime]) {
        vis[prime] = true;
        lsPrime.push_back(prime);
      }
    }
  }
  for (long long prime : lsPrime) {
    Pos[prime].push_back(n + 1);
    reverse(Pos[prime].begin(), Pos[prime].end());
    vis[prime] = false;
  }
}
long long Pow(long long a, long long b) {
  long long ans = 1;
  for (; b > 0; b /= 2, a = (a * a) % MOD)
    if (b % 2 == 1) ans = (ans * a) % MOD;
  return ans;
}
long long ans[N], rez[N];
struct Binary_Indexed_Tree {
  long long node[N];
  Binary_Indexed_Tree() {
    for (long long i = 0; i < N; ++i) node[i] = 1;
  }
  void update(long long pos, long long val) {
    for (long long i = pos; i <= n; i += i & (-i))
      node[i] = (node[i] * val) % MOD;
  }
  long long get(long long pos) {
    long long ans = 1;
    for (long long i = pos; i > 0; i -= i & (-i)) ans = (ans * node[i]) % MOD;
    return ans;
  }
} BIT;
void update(long long l, long long r, long long val) {
  if (l > r) return;
  long long inv = Pow(val, MOD - 2);
  BIT.update(l, val);
  BIT.update(r + 1, inv);
}
long long Mul[VAL], invMul[VAL], Product[N];
void sol() {
  sieve();
  prepare();
  for (long long prime : lsPrime) {
    Mul[prime] = (prime - 1) * Pow(prime, MOD - 2) % MOD;
    invMul[prime] = Pow(Mul[prime], MOD - 2);
  }
  for (long long i = 1; i <= n; ++i) {
    long long val = a[i];
    update(i, i, (i == 1) ? 1 : BIT.get(i - 1));
    while (val > 1) {
      long long prime = Div[val];
      while (val % prime == 0) val /= prime;
      if (vis[prime]) continue;
      vis[prime] = true;
      update(i, i, Mul[prime]);
    }
  }
  for (ii foo : ques[1]) rez[foo.id] = BIT.get(foo.r);
  for (long long i = 2; i <= n; ++i) {
    long long val = a[i - 1];
    while (val > 1) {
      long long prime = Div[val];
      while (val % prime == 0) val /= prime;
      Pos[prime].pop_back();
      update(i, Pos[prime].back() - 1, invMul[prime]);
    }
    for (ii foo : ques[i]) rez[foo.id] = BIT.get(foo.r);
  }
  Product[0] = 1;
  for (long long i = 1; i <= n; ++i) Product[i] = (Product[i - 1] * a[i]) % MOD;
  for (long long l = 1; l <= n; ++l)
    for (ii foo : ques[l]) {
      rez[foo.id] = rez[foo.id] * Product[foo.r] % MOD *
                    Pow(Product[l - 1], MOD - 2) % MOD;
    }
  for (long long i = 1; i <= Q; ++i) {
    Write(rez[i]), putchar('\n');
  }
}
int main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
  }
  Read(n);
  for (long long i = 1; i <= n; ++i) Read(a[i]);
  Read(Q);
  long long l, r;
  for (long long i = 1; i <= Q; ++i) {
    Read(l);
    Read(r);
    ques[l].push_back(ii(r, i));
  }
  sol();
  return 0;
}

```