#include<bits/stdc++.h>
#define blk(i) ((i-1)/B+1)
using namespace std;
const int N=100005,mod=19260817;
int n,m,V,l=1,r,res=1,ct1,ct2,a[N],B,P,pr[3405],f[40005],sum[1175][N],id[10005],rec[N<<2],ct[N];
pair<int,int> num[N][5];
long long ans[N];
unordered_map<int,int> Id;
struct node
{
	int l,r,id;
	bool operator<(node a)
	{
		if(blk(l)^blk(a.l))return blk(l)<blk(a.l);
		if(blk(l)&1)return r<a.r;
		return r>a.r;
	}
}q[N];
void getprime()
{
	int L=sqrt(V)+1;
	for(int i=2;i<=L;i++)
	{
		if(!f[i])
		{
			pr[++ct1]=i;
			if(i<=P)id[i]=ct1;
		}
		for(int j=1;j<=ct1&&i*pr[j]<=L;j++)
		{
			f[i*pr[j]]=true;
			if(i%pr[j]==0)break;
		}
	}
}
void getfac(int x,int k)
{
	for(int i=1;i<=ct1;i++)
	{
		if(pr[i]>P)break;
		sum[i][k]=sum[i][k-1];
	}
	for(int i=1,cnt;i<=ct1;i++)
	{
		if(x%pr[i])continue;
		cnt=0;
		while(x%pr[i]==0)
		{
			cnt++;
			x/=pr[i];
		}
		if(pr[i]<=P)sum[i][k]+=cnt;
		else if(!Id[pr[i]])
		{
			Id[pr[i]]=++ct2;
			num[k][++ct[k]]=make_pair(pr[i],cnt);
		}
	}
	if(x!=1)
	{
		if(x<=P)sum[id[x]][k]++;
		else if(!Id[x])
		{
			Id[x]=++ct2;
			num[k][++ct[k]]=make_pair(x,1);
		}
	}
}
void add(int u)
{
	for(int i=1,fi,se;i<=ct[u];i++)
	{
		fi=num[u][i].first;se=num[u][i].second;
		res/=(rec[fi]+1);
		rec[fi]+=se;
		res*=(rec[fi]+1);
	}
}
void del(int u)
{
	for(int i=1,fi,se;i<=ct[u];i++)
	{
		fi=num[u][i].first;se=num[u][i].second;
		res/=(rec[fi]+1);
		rec[fi]-=se;
		res*=(rec[fi]+1);
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],V=max(V,a[i]);
	B=sqrt(n);P=sqrt(n)*log2(max(V,1));
	getprime();
	for(int i=1;i<=n;i++)getfac(a[i],i);
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;
		ans[i]=1;
		q[i].id=i;
		for(int j=0;j<1175;j++)(ans[i]*=sum[j][q[i].r]-sum[j][q[i].l-1]+1)%=mod;
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=m;i++)
	{
		while(q[i].l<l)add(--l);
		while(q[i].r>r)add(++r);
		while(q[i].l>l)del(l++);
		while(q[i].r<r)del(r--);
		ans[q[i].id]*=res;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}

在 6pts~12pts 中游荡……