1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
const int Mod=1e9+7;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
vi lg;
struct psgt{
const int MAXN_VAL=2e5+5;
#define ls(p) T[p][0]
#define rs(p) T[p][1]
#define prod(p) T[p][2]
#define mid ((s+t)>>1)
private:
vector<std::array<int,3>> T;
vi rt;
int nt,n;
void pu(int p){prod(p)=1ll*prod(ls(p))*prod(rs(p))%Mod;}
public:
void print(int p){
if(!p)return;
printf("node %d:ls=%d rs=%d prod=%d\n",p,ls(p),rs(p),prod(p));
print(ls(p)),print(rs(p));
}
psgt(int _n=0,vi a={}){
n=_n;nt=0;
T.resize(MAXN_VAL*32);rt.resize(n+1);
std::function<void(int&,int,int)> bu=[&](int& p,int s,int t){
p=++nt;
if(s==t)return prod(p)=1,void();
bu(ls(p),s,mid),bu(rs(p),mid+1,t),pu(p);
};bu(rt[0],1,n);
vi pre(MAXN_VAL,0);
std::function<void(int&,int,int,int,int,int)>
ins=[&](int& p,int ver,int pos,int x,int s,int t){
nt++;T[nt]=T[ver];p=nt;
if(s==t)return prod(p)=x,void();
if(pos<=mid)ins(ls(p),ls(ver),pos,x,s,mid);
else ins(rs(p),rs(ver),pos,x,mid+1,t);
pu(p);
};
for(int i=1;i<=n;++i){
rt[i]=rt[i-1];
if(a[i]>1){
if(pre[a[i]]>0)ins(rt[i],rt[i],pre[a[i]],1,1,n);
ins(rt[i],rt[i],i,a[i],1,n);
pre[a[i]]=i;
}
}
}
int qry(int l,int r){
std::function<int(int,int,int)> qr=[&](int p,int s,int t){
if(!p||l>t||s>r)return 1;
if(l<=s&&t<=r)return prod(p);
int ans=1ll*qr(ls(p),s,mid)*qr(rs(p),mid+1,t)%Mod;
return ans;
};return qr(rt[r],1,n);
}
#undef ls
#undef rs
#undef prod
#undef mid
};
struct stt{
const int MAXN=19;
private:
int n;
vector<vector<short>> st;
public:
stt(int _n=0,vector<short> a={}){
st.resize(MAXN,vector<short>((n=_n)+1));
st[0]=a;
for(int j=1;j<MAXN;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
st[j][i]=std::max(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
int qry(int l,int r){
int k=lg[r-l+1];
return std::max(st[k][l],st[k][r-(1<<k)+1]);
}
};
int ksm(int x,int y){
int ans=1;
for(;y;y>>=1,x=1ll*x*x%Mod)if(y&1)ans=1ll*ans*x%Mod;
return ans;
}
int main(){
int n=read();
vi a(n+1);
lg.resize(n+1);
lg[1]=0;
for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;++i)a[i]=read();
vi p={0};
int pt=0;
vector<bool> vis(500);
for(int i=2;pt<87;++i)if(!vis[i]){
p.push_back(i);
pt++;
for(int j=i*2;j<500;j+=i)vis[j]=1;
}
vector<vector<short>> ps(pt+1,vector<short>(n+1));
for(int i=1;i<=n;++i)
for(int j=1;j<=pt;++j)
for(;a[i]%p[j]==0;a[i]/=p[j])ps[j][i]++;
psgt pst(n,a);
vector<stt> st;st.push_back(stt());
for(int i=1;i<=pt;++i)st.push_back(stt(n,ps[i]));
int q=read(),ans=0;
while(q--){
int l=(read()+ans)%n+1,r=(read()+ans)%n+1;
if(l>r)std::swap(l,r);
ans=pst.qry(l,r);
for(int i=1;i<=pt;++i)ans=1ll*ans*ksm(p[i],st[i].qry(l,r))%Mod;
printf("%d\n",ans);
}
return 0;
}
|