#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 100005
#define M 500
const int mod=19260817;
int prime[1400005],tot;
int inv[500005];
bool vis[20000005];
void shai()
{
	vis[1]=1;
	int i,j;
	for(i=2;i<=20000000;i++){
		if(!vis[i])prime[++tot]=i;
		for(j=1;j<=tot;j++){
			int tmp=i*prime[j];
			if(tmp>20000000)break;
			vis[tmp]=1;
			if(i%prime[j]==0)break;
		}
	}
	inv[1]=inv[0]=1;
	for(i=2;i<=500000;i++)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
 
int pr[105],pcnt;
int a[N][5],cnt[N],hh[5*N],hcnt;
int sum[100][N];
inline int ksm(int x,int y,int p)
{
	int ret=1;
	while(y){
		if(y&1)ret=1ll*x*ret%p;
		y>>=1;x=1ll*x*x%p;
	}
	return ret;
}
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int bas[6]={3,7,37,79,97,19260817};
inline bool mler(int n)
{
	if(n<=20000000)return vis[n]^1;
	int r=n-1,t=0;
	while(!(r&1))r>>=1,t++;
	for(int i=0;i<6;i++){
		if(n==bas[i])return 1;
		int now,pre=ksm(bas[i],r,n);
		for(int k=0;k<t;swap(now,pre),k++)
			if((now=1ll*pre*pre%n)==1&&pre!=1&&pre!=n-1)
				return 0;
		if(pre!=1)return 0;
	}
	return 1;
}
/*inline int ab(int x){return x<0?-x:x;}
int rho(int n,int c)
{
	int i=1,j=0,x=rand()%(n-1)+1,y=x;
	int d=1,tmp=1;
	while(d==1){
		x=(1ll*x*x+c)%mod;
		tmp=1ll*tmp*ab(y-x)%mod;
		if(++j==i)i<<=1,y=x,d=gcd(tmp,n);
		if(!(j&127))d=gcd(tmp,n);
	}
	return d==n?rho(n,c+1):d;
}
void plar(int n)
{
	if(n==1)return;
	if(mler(n)){pr[++pcnt]=n;return;}
	int d=rho(n,3);
	plar(d);plar(n/d);
}*/
#define D 366
int tong[5*N],ans[N];
struct node{
	int l,r,id;
}q[N];
inline bool cmp(const node &x,const node &y){int t=(x.l)/D;return t<(y.l/D)||(t==(y.l/D)&&(((t&1)&&x.r<y.r)||(!(t&1)&&x.r>y.r)));}
inline int query(int l,int r)
{
	int ret=1;
	for(int i=1;i<=95;i++)
		ret=1ll*ret*(sum[i][r]-sum[i][l-1]+1)%mod;
	return ret;
}
//#include<ctime>
//double c1;
int main()
{
	//c1=clock();
	//freopen("1.in","r",stdin);
	
	srand(0);shai();
	int n,i,j,m,x,l,r,mul,tmp;
	n=gi();m=gi();
	for(i=1;i<=n;i++){
		x=gi();//printf("%d\n",i);
		bool flg;
		if(x>500&&mler(x)){
			a[i][++cnt[i]]=x;
			hh[++hcnt]=x;
			//printf("%d\n",x);
			continue;
		}
		for(j=1;j<=95&&x>1;j++){
			flg=0;
			while(x%prime[j]==0){
				sum[j][i]++;
				x/=prime[j];
				//printf("%d ",prime[j]);
				flg=1;
			}
		}
		if(x>500&&mler(x)){
			a[i][++cnt[i]]=x;
			hh[++hcnt]=x;
			//printf("%d\n",x);
			continue;
		}
		for(j=96;1ll*prime[j]*prime[j]<=x&&x>1;j++){
			flg=0;
			while(x%prime[j]==0){
				a[i][++cnt[i]]=prime[j];
				hh[++hcnt]=prime[j];
				//printf("%d ",prime[j]);
				x/=prime[j];
				flg=1;
			}
			if(flg&&mler(x))break;
		}
		if(x>500){
			a[i][++cnt[i]]=x;
			hh[++hcnt]=x;
		}
		//printf("%d\n",x);
		/*pcnt=0;plar(x);
		for(j=1;j<=pcnt;j++){
			a[i][++cnt[i]]=pr[j];
			hh[++hcnt]=pr[j];
			//printf("%d ",pr[j]);
		}*/
	}
	sort(hh+1,hh+hcnt+1);
	hcnt=unique(hh+1,hh+hcnt+1)-hh-1;
	for(i=1;i<=n;i++)
		for(j=1;j<=cnt[i];j++)
			a[i][j]=lower_bound(hh+1,hh+hcnt+1,a[i][j])-hh;
	for(i=1;i<=95;i++)
		for(j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1];
			if(sum[i][j]>=mod)sum[i][j]-=mod;
		}
	for(i=1;i<=m;i++){q[i].l=gi();q[i].r=gi();q[i].id=i;if(q[i].l>q[i].r)swap(q[i].l,q[i].r);}
	sort(q+1,q+m+1,cmp);
	
	mul=1;l=1;r=0;
	
	//printf("%.3fs\n",(clock()-c1)/1000);
	//freopen("1.out","w",stdout);
	for(i=1;i<=m;i++){
		while(l>q[i].l){
			l--;
			for(j=1;j<=cnt[l];j++){
				tmp=(++tong[a[l][j]]);
				mul=1ll*mul*inv[tmp]%mod*(tmp+1)%mod;
			}
		}
		while(r<q[i].r){
			r++;
			for(j=1;j<=cnt[r];j++){
				tmp=(++tong[a[r][j]]);
				mul=1ll*mul*inv[tmp]%mod*(tmp+1)%mod;
			}
		}
		while(l<q[i].l){
			for(j=1;j<=cnt[l];j++){
				tmp=(--tong[a[l][j]]);
				mul=1ll*mul*inv[tmp+2]%mod*(tmp+1)%mod;
			}
			l++;
		}
		while(r>q[i].r){
			for(j=1;j<=cnt[r];j++){
				tmp=(--tong[a[r][j]]);
				mul=1ll*mul*inv[tmp+2]%mod*(tmp+1)%mod;
			}
			r--;
		}
		ans[q[i].id]=1ll*mul*query(l,r)%mod;
	}
	for(i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	//freopen("CON","w",stdout);
	//printf("%.3fs\n",(clock()-c1)/1000);
}