#include <bits/stdc++.h>
using namespace std;
struct query {
  int l, r, i;
} q[200010];
long long rez[200010], tree[4 * 200010], inv[1000010], a[200010], val, ans,
    maxval;
int where[1000010], l, r, n, m;
vector<int> comp[1000010];
bool querySort(query a, query b) { return a.r < b.r; }
void sieve(int n) {
  for (int i = 2; i <= n; ++i) {
    if (comp[i].size() == 0) {
      for (int j = i; j <= n; j += i) {
        comp[j].push_back(i);
      }
    }
  }
}
void createTree(int node, int left, int right) {
  if (left == right) {
    tree[node] = a[left];
    return;
  }
  int mid = (left + right) >> 1;
  createTree(node << 1, left, mid);
  createTree((node << 1) + 1, mid + 1, right);
  tree[node] = tree[node << 1] * tree[(node << 1) + 1] % 1000000007;
}
void update(int node, int left, int right) {
  if (left == right) {
    tree[node] = tree[node] * val % 1000000007;
    return;
  }
  int mid = (left + right) >> 1;
  if (l <= mid)
    update(node << 1, left, mid);
  else
    update((node << 1) + 1, mid + 1, right);
  tree[node] = tree[node << 1] * tree[(node << 1) + 1] % 1000000007;
}
void query(int node, int left, int right) {
  if (l <= left && right <= r) {
    ans = ans * tree[node] % 1000000007;
    return;
  }
  int mid = (left + right) >> 1;
  if (l <= mid) query(node << 1, left, mid);
  if (r > mid) query((node << 1) + 1, mid + 1, right);
}
void place(int p) {
  int x = a[p];
  for (int i = 0; i < comp[x].size(); ++i) {
    long long fac = comp[x][i];
    if (where[fac] != 0) {
      l = where[fac];
      val = fac * inv[fac - 1] % 1000000007;
      update(1, 1, n);
    }
    l = p;
    val = inv[fac] * (fac - 1) % 1000000007;
    update(1, 1, n);
    where[fac] = p;
  }
}
void getInverses(int n) {
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = -1000000007 / i * inv[1000000007 % i] % 1000000007 + 1000000007;
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    maxval = max(maxval, a[i]);
  }
  createTree(1, 1, n);
  sieve(maxval);
  getInverses(maxval);
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> q[i].l >> q[i].r;
    q[i].i = i;
  }
  sort(q + 1, q + m + 1, querySort);
  int index = 1;
  for (int i = 1; i <= m; ++i) {
    while (index <= q[i].r) {
      place(index);
      ++index;
    }
    ans = 1;
    l = q[i].l;
    r = q[i].r;
    query(1, 1, n);
    rez[q[i].i] = ans;
  }
  for (int i = 1; i <= m; ++i) {
    cout << rez[i] << "\n";
  }
}

### Prompt

Please provide a Cpp coded solution 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;
struct query {
  int l, r, i;
} q[200010];
long long rez[200010], tree[4 * 200010], inv[1000010], a[200010], val, ans,
    maxval;
int where[1000010], l, r, n, m;
vector<int> comp[1000010];
bool querySort(query a, query b) { return a.r < b.r; }
void sieve(int n) {
  for (int i = 2; i <= n; ++i) {
    if (comp[i].size() == 0) {
      for (int j = i; j <= n; j += i) {
        comp[j].push_back(i);
      }
    }
  }
}
void createTree(int node, int left, int right) {
  if (left == right) {
    tree[node] = a[left];
    return;
  }
  int mid = (left + right) >> 1;
  createTree(node << 1, left, mid);
  createTree((node << 1) + 1, mid + 1, right);
  tree[node] = tree[node << 1] * tree[(node << 1) + 1] % 1000000007;
}
void update(int node, int left, int right) {
  if (left == right) {
    tree[node] = tree[node] * val % 1000000007;
    return;
  }
  int mid = (left + right) >> 1;
  if (l <= mid)
    update(node << 1, left, mid);
  else
    update((node << 1) + 1, mid + 1, right);
  tree[node] = tree[node << 1] * tree[(node << 1) + 1] % 1000000007;
}
void query(int node, int left, int right) {
  if (l <= left && right <= r) {
    ans = ans * tree[node] % 1000000007;
    return;
  }
  int mid = (left + right) >> 1;
  if (l <= mid) query(node << 1, left, mid);
  if (r > mid) query((node << 1) + 1, mid + 1, right);
}
void place(int p) {
  int x = a[p];
  for (int i = 0; i < comp[x].size(); ++i) {
    long long fac = comp[x][i];
    if (where[fac] != 0) {
      l = where[fac];
      val = fac * inv[fac - 1] % 1000000007;
      update(1, 1, n);
    }
    l = p;
    val = inv[fac] * (fac - 1) % 1000000007;
    update(1, 1, n);
    where[fac] = p;
  }
}
void getInverses(int n) {
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = -1000000007 / i * inv[1000000007 % i] % 1000000007 + 1000000007;
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    maxval = max(maxval, a[i]);
  }
  createTree(1, 1, n);
  sieve(maxval);
  getInverses(maxval);
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> q[i].l >> q[i].r;
    q[i].i = i;
  }
  sort(q + 1, q + m + 1, querySort);
  int index = 1;
  for (int i = 1; i <= m; ++i) {
    while (index <= q[i].r) {
      place(index);
      ++index;
    }
    ans = 1;
    l = q[i].l;
    r = q[i].r;
    query(1, 1, n);
    rez[q[i].i] = ans;
  }
  for (int i = 1; i <= m; ++i) {
    cout << rez[i] << "\n";
  }
}

```