#include <bits/stdc++.h>
using namespace std;
long long bigmod(long long b, int p) {
  if (p == 0) return 1;
  long long my = bigmod(b, p / 2);
  my *= my;
  my %= 1000000007;
  if (p & 1) my *= b, my %= 1000000007;
  return my;
}
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
struct info {
  int x, y, idx;
  bool operator<(const info &p) const { return y < p.y; }
};
vector<info> qlist[1000005];
int n, N, ara[1000005], dvs[1000005][7], c[1000005], cum[1000005], lol[1000005];
bool pra[1000005], cnt[1000005], taken[1000005];
void sieve() {
  int i, j;
  pra[1] = 1;
  for (i = 2; i <= 1000000; i++) {
    if (pra[i] == 0) {
      for (j = i; j <= 1000000; j += i) {
        if (i != j) pra[j] = 1;
        dvs[j][c[j]++] = i;
      }
    }
  }
}
map<int, bool> mp;
vector<int> v[1000005], latest[1000005];
int pos[1000005], mx;
void prework() {
  int i, j, k, s = 0;
  for (i = 0; i < n; i += N) {
    for (j = i; j < i + N && j < n; j++) {
      int my = ara[j];
      for (k = 0; k < c[my]; k++) {
        int d = dvs[my][k];
        if (taken[d] == 0) {
          taken[d] = 1;
          v[s].push_back(d);
        }
        pos[d] = j;
      }
    }
    int len = v[s].size();
    for (j = 0; j < len; j++) {
      int d = v[s][j];
      latest[s].push_back(pos[d]);
    }
    mx = max(len, mx);
    s++;
    memset(taken, 0, sizeof(taken));
  }
}
int A, B;
void add(int idx) {
  int i, my = ara[idx], len = c[my];
  long long AA = A, BB = B;
  for (i = 0; i < len; i++) {
    int d = dvs[my][i];
    if (cnt[d] == 0) {
      AA *= (d - 1);
      AA %= 1000000007;
      BB *= d;
      BB %= 1000000007;
      cnt[d] = 1;
    }
  }
  A = (int)AA;
  B = (int)BB;
}
int abyb(int a, int b) {
  return (int)(((long long)a * bigmod((long long)b, 1000000007 - 2)) %
               1000000007);
}
int go(int id, int x, int y) {
  long long a = 1, b = 1, tot = 1;
  int i, j;
  for (i = x; i <= y; i++) {
    int my = ara[i], len = c[my];
    for (j = 0; j < len; j++) {
      int d = dvs[my][j];
      if (taken[d] == 0) {
        a *= (d - 1);
        a %= 1000000007;
        b *= d;
        b %= 1000000007;
        taken[d] = 1;
      }
    }
    tot *= my;
    tot %= 1000000007;
  }
  int s = v[id].size();
  for (i = 0; i < s; i++) taken[v[id][i]] = 0;
  return (int)((abyb(tot, b) * a) % 1000000007);
}
int fuck;
int fun(int idx, int x, int r) {
  int y = (idx + 1) * N - 1;
  if (y >= n) y = n - 1;
  long long a = 1, b = 1;
  int i, j;
  int s = v[idx].size();
  for (i = 0; i < s; i++) {
    int d = v[idx][i];
    int l = latest[idx][i];
    if (l >= x && cnt[d] == 0) {
      a *= (d - 1);
      a %= 1000000007;
      b *= d;
      b %= 1000000007;
    }
  }
  int tot = cum[r];
  if (x) tot = abyb(tot, cum[x - 1]);
  a *= A;
  a %= 1000000007;
  b *= B;
  b %= 1000000007;
  return (int)((abyb(tot, b) * a) % 1000000007);
}
char az[1000005][10];
int main() {
  char str[10];
  sieve();
  int q;
  int i, j, k, x, y;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s", str);
    ara[i] = atoi(str);
    if (!i)
      cum[i] = ara[i];
    else {
      long long my = ((long long)cum[i - 1] * ara[i]) % 1000000007;
      cum[i] = (int)my;
    }
  }
  N = sqrt(n) * 3;
  if (N < 1) N = 1;
  prework();
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    scanf("%s", str);
    x = atoi(str);
    scanf("%s", str);
    y = atoi(str);
    x--;
    y--;
    info tmp;
    tmp.x = x;
    tmp.y = y;
    tmp.idx = i;
    int my = x / N;
    qlist[my].push_back(tmp);
  }
  int s = n / N + 1;
  for (i = 0; i < s; i++) sort(qlist[i].begin(), qlist[i].end());
  int f = 0;
  for (i = 0; i < s; i++) {
    int len = qlist[i].size();
    int r = (i + 1) * N - 1;
    A = B = 1;
    memset(cnt, 0, sizeof(cnt));
    int C = (i + 1) * N;
    for (j = 0; j < len; j++) {
      f++;
      info my = qlist[i][j];
      x = my.x;
      y = my.y;
      int idx = my.idx;
      if (y < C) {
        int ans = go(i, x, y);
        lol[my.idx] = ans;
      } else {
        for (k = r + 1; k <= y; k++) add(k);
        r = y;
        int ans = fun(i, x, y);
        lol[my.idx] = ans;
      }
    }
  }
  for (i = 1; i <= q; i++) {
    printf("%d", lol[i]);
    printf("\n");
  }
  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;
long long bigmod(long long b, int p) {
  if (p == 0) return 1;
  long long my = bigmod(b, p / 2);
  my *= my;
  my %= 1000000007;
  if (p & 1) my *= b, my %= 1000000007;
  return my;
}
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
struct info {
  int x, y, idx;
  bool operator<(const info &p) const { return y < p.y; }
};
vector<info> qlist[1000005];
int n, N, ara[1000005], dvs[1000005][7], c[1000005], cum[1000005], lol[1000005];
bool pra[1000005], cnt[1000005], taken[1000005];
void sieve() {
  int i, j;
  pra[1] = 1;
  for (i = 2; i <= 1000000; i++) {
    if (pra[i] == 0) {
      for (j = i; j <= 1000000; j += i) {
        if (i != j) pra[j] = 1;
        dvs[j][c[j]++] = i;
      }
    }
  }
}
map<int, bool> mp;
vector<int> v[1000005], latest[1000005];
int pos[1000005], mx;
void prework() {
  int i, j, k, s = 0;
  for (i = 0; i < n; i += N) {
    for (j = i; j < i + N && j < n; j++) {
      int my = ara[j];
      for (k = 0; k < c[my]; k++) {
        int d = dvs[my][k];
        if (taken[d] == 0) {
          taken[d] = 1;
          v[s].push_back(d);
        }
        pos[d] = j;
      }
    }
    int len = v[s].size();
    for (j = 0; j < len; j++) {
      int d = v[s][j];
      latest[s].push_back(pos[d]);
    }
    mx = max(len, mx);
    s++;
    memset(taken, 0, sizeof(taken));
  }
}
int A, B;
void add(int idx) {
  int i, my = ara[idx], len = c[my];
  long long AA = A, BB = B;
  for (i = 0; i < len; i++) {
    int d = dvs[my][i];
    if (cnt[d] == 0) {
      AA *= (d - 1);
      AA %= 1000000007;
      BB *= d;
      BB %= 1000000007;
      cnt[d] = 1;
    }
  }
  A = (int)AA;
  B = (int)BB;
}
int abyb(int a, int b) {
  return (int)(((long long)a * bigmod((long long)b, 1000000007 - 2)) %
               1000000007);
}
int go(int id, int x, int y) {
  long long a = 1, b = 1, tot = 1;
  int i, j;
  for (i = x; i <= y; i++) {
    int my = ara[i], len = c[my];
    for (j = 0; j < len; j++) {
      int d = dvs[my][j];
      if (taken[d] == 0) {
        a *= (d - 1);
        a %= 1000000007;
        b *= d;
        b %= 1000000007;
        taken[d] = 1;
      }
    }
    tot *= my;
    tot %= 1000000007;
  }
  int s = v[id].size();
  for (i = 0; i < s; i++) taken[v[id][i]] = 0;
  return (int)((abyb(tot, b) * a) % 1000000007);
}
int fuck;
int fun(int idx, int x, int r) {
  int y = (idx + 1) * N - 1;
  if (y >= n) y = n - 1;
  long long a = 1, b = 1;
  int i, j;
  int s = v[idx].size();
  for (i = 0; i < s; i++) {
    int d = v[idx][i];
    int l = latest[idx][i];
    if (l >= x && cnt[d] == 0) {
      a *= (d - 1);
      a %= 1000000007;
      b *= d;
      b %= 1000000007;
    }
  }
  int tot = cum[r];
  if (x) tot = abyb(tot, cum[x - 1]);
  a *= A;
  a %= 1000000007;
  b *= B;
  b %= 1000000007;
  return (int)((abyb(tot, b) * a) % 1000000007);
}
char az[1000005][10];
int main() {
  char str[10];
  sieve();
  int q;
  int i, j, k, x, y;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s", str);
    ara[i] = atoi(str);
    if (!i)
      cum[i] = ara[i];
    else {
      long long my = ((long long)cum[i - 1] * ara[i]) % 1000000007;
      cum[i] = (int)my;
    }
  }
  N = sqrt(n) * 3;
  if (N < 1) N = 1;
  prework();
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    scanf("%s", str);
    x = atoi(str);
    scanf("%s", str);
    y = atoi(str);
    x--;
    y--;
    info tmp;
    tmp.x = x;
    tmp.y = y;
    tmp.idx = i;
    int my = x / N;
    qlist[my].push_back(tmp);
  }
  int s = n / N + 1;
  for (i = 0; i < s; i++) sort(qlist[i].begin(), qlist[i].end());
  int f = 0;
  for (i = 0; i < s; i++) {
    int len = qlist[i].size();
    int r = (i + 1) * N - 1;
    A = B = 1;
    memset(cnt, 0, sizeof(cnt));
    int C = (i + 1) * N;
    for (j = 0; j < len; j++) {
      f++;
      info my = qlist[i][j];
      x = my.x;
      y = my.y;
      int idx = my.idx;
      if (y < C) {
        int ans = go(i, x, y);
        lol[my.idx] = ans;
      } else {
        for (k = r + 1; k <= y; k++) add(k);
        r = y;
        int ans = fun(i, x, y);
        lol[my.idx] = ans;
      }
    }
  }
  for (i = 1; i <= q; i++) {
    printf("%d", lol[i]);
    printf("\n");
  }
  return 0;
}

```