// luogu-judger-enable-o2
/*
QAQ
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e5+100,M=1e6+100;
const ll mod=19260817;
int prime[M],mp[M];
int pos[N],a[N];
ll ans[N],out;
int n,m;
int ssp[N][200],sum[N][200];
vector<int>Q;
bool v[N];
struct node{
    int l,r,now;
    bool operator < (const node &a)const
    {
        if(pos[l]!=pos[a.l]) return pos[l]<pos[a.l];
        return r<a.r;
    }
} s[N];

void ins(int x)
{
    if(a[x]==1) return;
    out*=prime[mp[a[x]]+1];
    out%=mod;
    mp[a[x]]++;
    out*=mp[a[x]]+1;
    out%=mod;
}

void del(int x)
{
    if(a[x]==1) return;
    out*=prime[mp[a[x]]+1];
    out%=mod;
    mp[a[x]]--;
    out*=mp[a[x]]+1;
    out%=mod;
}

int main()
{
    memset(v,false,sizeof(v));
    prime[1]=1;
    for(int i=2;i<=M;i++) prime[i]=(ll)(mod-mod/i)*prime[mod%i]%mod;
    for(int i=2;i<=1000;i++)
    {
        if(!v[i]) Q.push_back(i);
        for(int j=i+i;j<=1000;j+=i) v[j]=true;
    }
    scanf("%d %d",&n,&m);
    memset(mp,0,sizeof(mp));
    out=1;
    int k=sqrt(n);
    for(ll i=1;i<=n;i++)
    {
        pos[i]=(i-1)/k+1;
        scanf("%d",&a[i]);
        int temp=a[i];
        for(int j=0;j<Q.size();j++)
            while(temp%Q[j]==0)
            {
                temp/=Q[j];
                ssp[i][j]++;
            }
        for(int j=0;j<Q.size();j++) sum[i][j]=sum[i-1][j]+ssp[i][j];
        a[i]=temp;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&s[i].l,&s[i].r);
        s[i].now=i;
    }
    sort(s+1,s+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(r>s[i].r) del(r),r--;
        while(r<s[i].r) r++,ins(r);
        while(l<s[i].l) del(l),l++;
        while(l>s[i].l) l--,ins(l);
        ll q=1;
        for(int j=0;j<Q.size();j++)
        {
            q*=sum[s[i].r][j]-sum[s[i].l-1][j]+1;
            q%=mod;
        }
        ans[s[i].now]=(out*q)%mod;
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}