#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define il inline

 #define N 50010

 #define maxn 1000000

 #define mod 1000777

 using namespace std;

 int n,q,ctp,tot;

 int root[N];

 int pr[maxn+],use[maxn+],lst[maxn+];

 ll a[N],inv[mod+],nxt[maxn+];

 struct Seg{ll sum;int ls,rs;}seg[N*]; //re

 void prime_inv()

 {

     for(int i=;i<=maxn;i++)

     {

         if(!use[i])

             pr[++ctp]=i,nxt[i]=i;

         for(int j=;j<=ctp&&i*pr[j]<=maxn;j++){

             use[i*pr[j]]=,nxt[i*pr[j]]=pr[j];

             if(i%pr[j]==) break;

         }

     }

     inv[]=inv[]=;

     for(ll i=;i<mod;i++)

         inv[i]=(mod-mod/i)*inv[mod%i]%mod;

 }

 ll gc()

 {

     ll ret=,fh=;char p=getchar();

     while(p<''||p>'') {if(p=='-')fh=-;p=getchar();}

     while(p>=''&&p<='') {ret=(ret<<)+(ret<<)+p-'';p=getchar();}

     return ret*fh;

 }

 il void pushup(int rt){seg[rt].sum=(seg[seg[rt].ls].sum*seg[seg[rt].rs].sum)%mod;}

 void build(int l,int r,int rt)

 {

     seg[rt].sum=;

     if(l==r)return;

     int mid=(l+r)>>;

     seg[rt].ls=++tot,build(l,mid,tot);

     seg[rt].rs=++tot,build(mid+,r,tot);

 }

 void update(int x,int l,int r,int rt1,int rt2,ll w)

 {

     if(l==r) {seg[rt2].sum=(seg[rt2].sum*w)%mod;return;}

     int mid=(l+r)>>;

     if(x<=mid)

     {

         if(!seg[rt2].ls||seg[rt1].ls==seg[rt2].ls){

             seg[rt2].ls=++tot,seg[seg[rt2].ls].sum=seg[seg[rt1].ls].sum;

         if(!seg[rt2].rs)

             seg[rt2].rs=seg[rt1].rs;

         }

         update(x,l,mid,seg[rt1].ls,seg[rt2].ls,w);

     }else{

         if(!seg[rt2].rs||seg[rt1].rs==seg[rt2].rs){

             seg[rt2].rs=++tot,seg[seg[rt2].rs].sum=seg[seg[rt1].rs].sum;

         if(!seg[rt2].ls)

             seg[rt2].ls=seg[rt1].ls;

         }

         update(x,mid+,r,seg[rt1].rs,seg[rt2].rs,w);

     }

     pushup(rt2);

 }

 ll query(int L,int R,int l,int r,int rt)

 {

     if(L<=l&&r<=R) return seg[rt].sum;

     int mid=(l+r)>>;ll ans=;

     if(L<=mid) ans*=query(L,R,l,mid,seg[rt].ls),ans%=mod;

     if(R>mid) ans*=query(L,R,mid+,r,seg[rt].rs),ans%=mod;

     return ans;

 }

 int main()

 {

     //freopen("a.in","r",stdin);

     //freopen("a.out","w",stdout);

     scanf("%d%d",&n,&q);

     for(int i=;i<=n;i++) a[i]=gc();

     prime_inv();

     root[]=++tot;

     build(,n,);

     ll x,p,w;

     for(int i=;i<=n;i++)

     {

         x=a[i],w=a[i],root[i]=++tot;

         while(x!=){

             p=nxt[x];

             if(lst[p])

                 update(lst[p],,n,root[i-],root[i],(inv[p-]*p)%mod);

             lst[p]=i;

             x/=p,w=((w*(p-(ll))%mod)*inv[p])%mod;

             while(x%p==) x/=p;

         }

         update(i,,n,root[i-],root[i],w);

     }

     ll l,r,ans=;

     for(int i=;i<=q;i++)

     {

         l=gc(),r=gc();

         l^=ans,r^=ans;

         ans=query(l,r,,n,root[r]);

         printf("%lld\n",ans);

     }

     return ;

 }