#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,mod=19260817;
int ksm(int x,int n,int mod){
	int ret=1;
	while(n){
		if(n%2){
			ret=ret*x%mod;
		}
		x=x*x%mod,n/=2;
	}
	return ret;
} 
int n,m,a[N],p[]={2,3,5,7,11,13,17,37},ans[N],now=1;
struct query{
	int l,r,id;
}q[N];
int belong(int x){
	int block=sqrt(n);
	return x/block+1;
}
int cmp(query x,query y){
	if(belong(x.l)!=belong(y.l)){
		return belong(x.l)<belong(y.l);
	}
	return x.r<y.r;
}
map<int,int>cnt;
int test(int n,int a){
	int d=n-1,r=0;
	while(d%2==0){
		d/=2,r++;
	}
	int num=ksm(a,d,n);
	if(num==1){
		return 1;
	}
	while(r--){
		if(num==n-1){
			return 1;
		}
		num=num*num%n;
	}
	return 0;
}
int prime(int n){
	if(n<=1){
		return 0;
	}
	for(int i:p){
		if(n==i){
			return 1;
		}
		if(n%i==0||!test(n,i)){
			return 0;
	    }
	}
	return 1;
}
int f(int x,int c,int n){
	return (x*x+c)%n;
}
mt19937 rnd(time(0));
int pollard(int n){
	int x=0,y=0,c=rnd()%(n-1)+1;
	for(int i=1;;i*=2){
		int val=1;
		x=y;
		for(int j=1;j<=i;j++){
			y=f(y,c,n),val=val*abs(x-y)%n;
			if(j%127==0){
				int d=__gcd(val,n);
				if(d>1){
					return d;
				}
			}
		}
		int d=__gcd(val,n);
		if(d>1){
			return d;
		}
	}
	return n;
}
int inv(int x){
	return ksm(x,mod-2,mod);
}
vector<int>vec[N];
void add(int x){
	for(int i:vec[x]){
		now=now*inv(cnt[i]+1)%mod,cnt[i]++,now=now*(cnt[i]+1)%mod;
	}
}
void del(int x){
	for(int i:vec[x]){
		now=now*inv(cnt[i]+1)%mod,cnt[i]--,now=now*(cnt[i]+1)%mod;
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		queue<int>q;
		q.push(a[i]);
		while(!q.empty()){
			int x=q.front();
			q.pop();
		    if(x==1){
		    	continue;
			}	
			if(prime(x)){
				vec[i].push_back(x);
				continue;
			}
			int num=pollard(x);
			while(num==x){
				num=pollard(x);
			}
			q.push(num),q.push(x/num);
		}
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r,q[i].id=i;
	} 
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l<q[i].l){
			del(l++);
		}
		while(l>q[i].l){
			add(--l);
		}
		while(r<q[i].r){
			add(++r);
		}
		while(r>q[i].r){
			del(r--);
		}
		ans[q[i].id]=now;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<'\n';
	}
}