Code:
#include <bits/stdc++.h>
#define ll long long
#define maxn 50207
#define setIO(s) freopen(s".in","r",stdin)
#define mod 1000777
using namespace std;
struct Tree
{
int tot;
int lson[maxn*270],rson[maxn*270];
ll mul[maxn*270];
int ins(int x,int l,int r,int p,ll v)
{
int o=++tot;
lson[o]=lson[x],rson[o]=rson[x];
if(x) mul[o]=mul[x]*v%mod;
else mul[o]=v;
if(l==r) return o;
int mid=(l+r)>>1;
if(p<=mid) lson[o]=ins(lson[x],l,mid,p,v);
else rson[o]=ins(rson[x],mid+1,r,p,v);
return o;
}
ll query(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R) return mul[x];
ll re=1;
int mid=(l+r)>>1;
if(L<=mid) re=re*query(lson[x],l,mid,L,R)%mod;
if(R>mid) re=re*query(rson[x],mid+1,r,L,R)%mod;
return re;
}
}tr;
int cnt,n,m;
int prime[1000004],vis[1000004],pre[1000006],rt[maxn],cur[maxn];
ll arr[maxn],mul[maxn];
ll qpow(ll base,ll k)
{
ll re=1;
while(k)
{
if(k&1) re=re*base%mod;
base=base*base%mod;
k>>=1;
}
return re;
}
void Initialize(int N)
{
for(int i=2;i<=N;++i)
{
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&1ll*prime[j]*i<=N;++j)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
for(int i=1;i<=n;++i)
{
int x=arr[i],cc=0;
rt[i]=rt[i-1];
if(x==1)
{
rt[i]=tr.ins(rt[i-1],1,n,i,1);
continue;
}
cur[++cc]=rt[i];
for(int j=1;j<=cnt&&1ll*prime[j]*prime[j]<=x;++j)
{
if(x%prime[j]==0)
{
if(pre[prime[j]])
{
cur[cc+1]=tr.ins(cur[cc],1,n,pre[prime[j]],1ll*prime[j]*qpow((prime[j]-1), mod-2)%mod);
++cc;
}
cur[cc+1]=tr.ins(cur[cc],1,n,pre[prime[j]]=i,1ll*(prime[j]-1)*qpow(prime[j],mod-2)%mod);
++cc;
while(x%prime[j]==0) x/=prime[j];
}
}
if(x>1)
{
if(pre[x])
{
cur[cc+1]=tr.ins(cur[cc],1,n,pre[x],1ll*x*qpow((x-1), mod-2)%mod);
++cc;
}
cur[cc+1]=tr.ins(cur[cc],1,n,pre[x]=i,1ll*(x-1)*qpow(x,mod-2)%mod);
++cc;
}
rt[i]=cur[cc];
for(int i=1;i<=cc;++i) cur[i]=0;
}
}
int main()
{
// setIO("input");
scanf("%d%d",&n,&m);
int mx=0;
mul[0]=1;
for(int i=1;i<=n;++i)
{
scanf("%lld",&arr[i]);
mul[i]=mul[i-1]*arr[i]%mod;
mx=max(mx, (int)arr[i]);
}
Initialize(mx);
ll lastans=0;
for(int i=1;i<=m;++i)
{
// lastans=0;
int l,r;
scanf("%d%d",&l,&r);
l^=lastans,r^=lastans;
ll rev=qpow(mul[l-1],mod-2);
lastans=mul[r]*rev%mod*tr.query(rt[r],1,n,l,r)%mod;
printf("%lld\n",lastans);
}
return 0;
}