(operatorname{lcm}) 能被区间内的每个数整除。考虑一个质数 (p)，它在 (a_i~(lle ile r)) 中的次数（质因数分解后 (p) 的指数）一定小于等于它在 (operatorname{lcm}) 中的次数。那么可以把 (operatorname{lcm}) 表示成 (prodlimits_{p ext{ 是质数}}p^{max{cnt_{i,p}}(lle ile r)})，其中 (cnt_{i,p}) 表示 (a_i) 中 (p) 的次数。
考虑根号分治。小于 (450) 的质数有 (87) 个，这些可以用 (87) 个 st 表做。
我们知道一个数 (x) 最多有一个大于 (sqrt x) 的质因子。把每个 (a_i) 中小于 (450) 的质因子全部除掉，剩下的是 (1) 或大于 (450) 的质数。
现在问题变成了求区间 ([l,r]) 中出现过的数的乘积（重复的只算一次）。设 (pre_i) 表示 ([1,i-1]) 中 (a_i) 最后一次出现的位置，没有出现则为 (0)。这个可以 (O(n)) 求。
对于一个 (i~(lle ile r))，若 (lle pre_i)，说明 ([l,i-1]) 中出现了一个与 (a_i) 相等的数，那么这个 (i) 是不能算贡献的。
问题又变成了 (prodlimits_{i=l}^r[pre_ile l-1]a_i)。考虑建 (n) 棵线段树，第 (j) 棵维护满足 (pre_ile j) 的数的乘积（(pre_i>j) 的位置上都为 (1)）。容易发现对于 (j~(j>0))，最多存在一个 (i) 满足 (pre_i=j)，也就是说从第 (j-1~(j>0)) 棵线段树到第 (j) 棵，最多只用修改一个数。那么可以用主席树做。
整体思路：
- 线性筛求质数
- 计算每个数中各个质数的次数并把它们除掉
- 建 ST 表
- 建主席树
- 回答询问
下面是代码（(pre) 没有用数组记录下来）
#include <cstdio>
using namespace std;
typedef long long ll;
inline int max(int x, int y) {return x > y ? x : y;}
inline int min(int x, int y) {return x < y ? x : y;}
inline void swap(int &x, int &y) {x ^= y ^= x ^= y;}
#define rei register int
#define rep(i, l, r) for(rei i = l, i##end = r; i <= i##end; ++i)
#define per(i, r, l) for(rei i = r, i##end = l; i >= i##end; --i)
#define ci const int
char inputbuf[1 << 23], *p1 = inputbuf, *p2 = inputbuf;
#define getchar() (p1 == p2 && (p2 = (p1 = inputbuf) + fread(inputbuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
int res = 0; char ch = getchar(); bool f = true;
for(; ch < '0' || ch > '9'; ch = getchar())
if(ch == '-') f = false;
for(; ch >= '0' && ch <= '9'; ch = getchar())
res = res * 10 + (ch ^ 48);
return f ? res : -res;
}
const int N = 2e5 + 15, SQRT = 450, P = 1e9 + 7;
int n, a[N], b[N], rt[N], tot, lg[N], lc[N * 20], rc[N * 20], pos[N * 2], pr[SQRT], cnt;
bool npr[SQRT];
char st[90][N][18];
ll mul[N * 18], poww[100][20];
inline void upd(int p) {
mul[p] = mul[lc[p]] * mul[rc[p]] % P;
}
void get_prime() {
npr[1] = 1;
rep(i, 2, SQRT - 1) {
if(!npr[i]) pr[++ cnt] = i;
for(rei j = 1; j <= cnt && i * pr[j] < SQRT; ++ j) {
npr[i * pr[j]] = 1;
if(i % pr[j] == 0) break;
}
}
}
inline int query(int k, int l, int r) {
int p = lg[r - l + 1];
return max(st[k][l][p], st[k][r - (1 << p) + 1][p]);
}
int build(int l, int r) {
int p = ++ tot, mid = l + r >> 1;
mul[p] = 1;
if(l == r) return p;
lc[p] = build(l, mid);
rc[p] = build(mid + 1, r);
return p;
}
void modify(int p, int l, int r, ci &t, ci &x) {
if(l == r) { mul[p] = x; return ; }
int mid = l + r >> 1;
if(t <= mid) modify(lc[p], l, mid, t, x);
else modify(rc[p], mid + 1, r, t, x);
upd(p);
}
int modify2(int rt, int l, int r, ci &t, ci &x) {
int p = ++ tot, mid = l + r >> 1;
if(l == r) { mul[p] = x; return p; }
if(t <= mid) lc[p] = modify2(lc[rt], l, mid, t, x), rc[p] = rc[rt];
else rc[p] = modify2(rc[rt], mid + 1, r, t, x), lc[p] = lc[rt];
upd(p);
return p;
}
ll query(int p, int l, int r, ci &tl, ci &tr) {
if(tl <= l && r <= tr) return mul[p];
int mid = l + r >> 1;
ll res = 1;
if(tl <= mid) res = query(lc[p], l, mid, tl, tr);
if(mid < tr) res = res * query(rc[p], mid + 1, r, tl, tr) % P;
return res;
}
void input() {
n = read();
rep(i, 1, n) {
a[i] = read();
rep(j, 1, cnt)
while(a[i] % pr[j] == 0) {
a[i] /= pr[j];
st[j][i][0] ++ ;
}
}
}
void build_st() {
rep(i, 2, n) lg[i] = lg[i / 2] + 1;
rep(k, 1, cnt) rep(j, 1, lg[n])
for(rei i = 1; i + (1 << j) - 1 <= n; ++ i)
st[k][i][j] = max(st[k][i][j - 1], st[k][i + (1 << j - 1)][j - 1]);
}
void build_sgt() {
rt[0] = build(1, n);
rep(i, 1, n) {
if(!pos[a[i]]) modify(rt[0], 1, n, i, a[i]);
else b[pos[a[i]]] = i;
pos[a[i]] = i;
}
rep(i, 1, n) {
if(b[i]) rt[i] = modify2(rt[i - 1], 1, n, b[i], a[b[i]]);
else rt[i] = rt[i - 1];
}
}
void solve() {
int l, r;
ll ans = 0;
rep(i, 1, cnt) {
poww[i][0] = 1;
rep(j, 1, 20) poww[i][j] = (poww[i][j - 1] * pr[i]) % P;
}
for(int q = read(); q; -- q) {
l = (read() + ans) % n + 1;
r = (read() + ans) % n + 1;
if(l > r) swap(l, r);
ans = 1;
rep(i, 1, cnt) ans = ans * poww[i][query(i, l, r)] % P;
ans = ans * query(rt[l - 1], 1, n, l, r) % P;
printf("%lld
", ans);
}
}
signed main() {
get_prime();
input();
build_st();
build_sgt();
solve();
return 0;
}