const mo=;

 type node=record

        po,next,num:longint;

      end;

      link=record

        l,r:longint;

        s1,s2:int64;

      end;

 var ni:array[..mo] of int64;

     s,sd:array[..] of int64;

     tree:array[..**] of link;

     p,v,last:array[..] of longint;

     e:array[..] of node;

     h,a,q:array[..] of longint;

     j,t,n,m,len,i,x,y,ans:longint;

     wh:int64;

 function build(l,r:longint):longint;

   var m,q:longint;

   begin

     inc(t);

     tree[t].s1:=;

     tree[t].s2:=;

     q:=t;

     if l<>r then

     begin

       m:=(l+r) shr ;

       tree[q].l:=build(l,m);

       tree[q].r:=build(m+,r);

     end;

     exit(q);

   end;

 function add(l,r,last,x,y:longint):longint;

   var m,q:longint;

   begin

     inc(t);

     q:=t;

     if l=r then

     begin

       tree[q].s1:=tree[last].s1*int64(y-) mod mo;

       tree[q].s2:=tree[last].s2*ni[y] mod mo;

     end

     else begin

       m:=(l+r) shr ;

       if x<=m then

       begin

         tree[q].r:=tree[last].r;

         tree[q].l:=add(l,m,tree[last].l,x,y);

       end

       else begin

         tree[q].l:=tree[last].l;

         tree[q].r:=add(m+,r,tree[last].r,x,y);

       end;

       tree[q].s1:=tree[tree[q].l].s1*tree[tree[q].r].s1 mod mo;

       tree[q].s2:=tree[tree[q].l].s2*tree[tree[q].r].s2 mod mo;

     end;

     exit(q);

   end;

 function get(a,b:link):int64;

   var p1,p2:int64;

   begin

     p1:=b.s1*ni[a.s1] mod mo;

     p2:=b.s2*ni[a.s2] mod mo;

     exit(p1*p2 mod mo);

   end;

 function ask(l,r,x,y,z:longint):longint;

   var m:longint;

       p,q:int64;

   begin

     if z>=r then exit(get(tree[x],tree[y]))

     else begin

       m:=(l+r) shr ;

       if z<=m then exit(ask(l,m,tree[x].l,tree[y].l,z))

       else begin

         p:=get(tree[tree[x].l],tree[tree[y].l]);

         q:=ask(m+,r,tree[x].r,tree[y].r,z);

         exit(p*q mod mo);

       end;

     end;

   end;

 begin

   for i:= to  do

   begin

     if v[i]= then

     begin

       inc(t);

       p[t]:=i;

       v[i]:=i;

     end;

     for j:= to t do

     begin

       if i*p[j]> then break;

       v[i*p[j]]:=p[j];

       if i mod p[j]= then break;

     end;

   end;

   ni[]:=;

   for i:= to mo- do

   begin

     ni[i]:=-int64(mo div i)*ni[mo mod i] mod mo;

     if ni[i]< then ni[i]:=(ni[i]+mo) mod mo;

   end;

   readln(n,m);

   s[]:=;

   sd[]:=;

   for i:= to n do

   begin

     read(a[i]);

     s[i]:=s[i-]*int64(a[i]) mod mo;

     sd[i]:=sd[i-]*int64(ni[a[i]]) mod mo;

     x:=a[i];

     while x<> do

     begin

       inc(len);

       y:=v[x];

       e[len].po:=y;

       e[len].num:=last[y];

       e[len].next:=q[i];

       q[i]:=len;

       last[y]:=i;

       while x mod y= do x:=x div y;

     end;

   end;

   t:=;

   tree[].s1:=;

   tree[].s2:=;

   h[]:=build(,n);

   for i:= to n do

   begin

     h[i]:=h[i-];

     j:=q[i];

     while j<> do

     begin

       y:=e[j].po;

       h[i]:=add(,n,h[i],e[j].num,y);

       j:=e[j].next;

     end;

   end;

   for i:= to m do

   begin

     readln(x,y);

     x:=x xor ans;

     y:=y xor ans;

     if x>y then

     begin

       t:=x; x:=y; y:=t;

     end;

     wh:=ask(,n,h[x-],h[y],x-);

     ans:=wh*s[y] mod mo*sd[x-] mod mo;

     if ans< then ans:=(ans+mo) mod mo;

     writeln(ans);

   end;

 end.