#12#13AC,其他WA

#include<bits/stdc++.h>
#define int long long
#define N 100009
#define K 209
using namespace std;
const int mod=19260817;
int n,m,a[N],ans[N],len,g[N],sum[N][K],primes[N],cnt,pri_id[N],now[K],Chtholly,res=1,inv[N*3];
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
pair<int,int>p[N];
bool st[N];
unordered_map<int,int>mp;
void init(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			primes[++cnt]=i;
			pri_id[i]=cnt;
		}
		for(int j=1;j<=cnt&&primes[j]*i<=n;j++){
			st[primes[j]*i]=1;
			if(i%primes[j]==0){
				break;
			}
		}
	}
}
void init_inv(int n){
	for(int i=1;i<=n;i++){
		inv[i]=ksm(i,mod-2);
	}
}
struct Node{
	int l,r,id;
}q[N];
int v[N],idx;
bool cmp(Node x,Node y){
	return g[x.l]==g[y.l]?x.r<y.r:g[x.l]<g[y.l];
}
int ksm(int x,int p,int mod){
	long long ans=1;
    while(p)
    {
        if(p&1)
            ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
bool second_felmat(int a,int p){
	int d=p-1,t=0;
	while(d&1^1){
		d>>=1;
		t++;
	}
	int before=ksm(a,d,p),now;
	for(int i=1;i<=t;i++){
		now=before*before%p;
		if(now==1&&before!=1&&before!=p-1){
			return 0;
		}
		before=now;
	}
	return (before==1);
}
bool miller_rabin(int x){
	if(x<=1){
		return 0;
	}
	if(x==2){
		return 1;
	}
	if(x&1^1){
		return 0;
	}
	for(int i=1;i<=5;i++){
		int a=rand()%(x-1)+1;
		if(!second_felmat(a,x)){
			return 0;
		}
	}
	return 1;
}
inline int f(int x,int c,int n){
	return (x*x+c)%n;
}
int pollard_rho(int x){
	int s=0,t=0,c=rand()%(x-1)+1,now=1;
	for(int limit=1;;limit<<=1){
		s=t,now=1;
		for(int i=1;i<=limit;i++){
			t=f(t,c,x);
			now=now*abs(t-s)%x;
			if(i%127==0){
				int d=__gcd(now,x);
				if(d>1){
					return d;
				}
			}
		}
		int d=__gcd(now,x);
		if(d>1){
			return d;
		}
	}
}
void resolve(int n){
	if(n<=1){
		return ;
	}
	if(miller_rabin(n)){
		v[++idx]=n;
		return ;
	}
	int divisor=n;
	while(divisor==n){
		divisor=pollard_rho(divisor);
	}
	while(n%divisor==0){
		n/=divisor;
	}
	resolve(divisor);resolve(n);
}
inline void add(int x){
	if(p[x].first){
		res=res*inv[now[p[x].first]+1]%mod;
		now[p[x].first]++;
		res=res*(now[p[x].first]+1)%mod;
	}
	if(p[x].second){
		res=res*inv[now[p[x].second]+1]%mod;
		now[p[x].second]++;
		res=res*(now[p[x].second]+1)%mod;
	}
}
inline void del(int x){
	if(p[x].first){
		res=res*inv[now[p[x].first]+1]%mod;
		now[p[x].first]--;
		res=res*(now[p[x].first]+1)%mod;
	}
	if(p[x].second){
		res=res*inv[now[p[x].second]+1]%mod;
		now[p[x].second]--;
		res=res*(now[p[x].second]+1)%mod;
	}
}
int calc(int l,int r){
	int ans=1;
	for(int i=1;i<=cnt;i++){
		ans=ans*(sum[r][i]-sum[l-1][i]+1)%mod;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	init(1000);
	cin>>n>>m;
	init_inv(n*3);
	len=sqrt(m);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		idx=0;
		resolve(a[i]);
		int x=a[i];
		for(int j=1;j<=idx;j++){
			if(v[j]>1000){
				if(!mp[v[j]]){
					mp[v[j]]=++Chtholly;
				}
				if(p[i].first){
					p[i].second=mp[v[j]];
					x/=v[j];
				}
				else{
					p[i].first=mp[v[j]];
					x/=v[j];
					if(x%v[j]==0){
						x/=v[j];
						p[i].second=mp[v[j]];
					}
				}
				continue;
			}
			int times=0;
			while(x%v[j]==0){
				x/=v[j];
				times++;
			}
			sum[i][pri_id[v[j]]]+=times;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt;j++){
			sum[i][j]+=sum[i-1][j];
		}
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
		g[i]=(i-1)/len+1;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>q[i].l){
			add(--l);
		}
		while(r<q[i].r){
			add(++r);
		}
		while(l<q[i].l){
			del(l++);
		}
		while(r>q[i].r){
			del(r--);
		}
		ans[q[i].id]=calc(l,r)*res%mod;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}