众所周知lxl是个毒瘤，Ynoi道道都是神仙题，题面好评

原题传送门

一看这题没有修改操作就知道这是莫队题（我也只会莫队）

我博客里对莫队的简单介绍

一个数N可以分解成\(p_1^{c_1}p_2^{c_2}…p_m^{c_m}\)

它的约数个数就是\((c_1+1)(c_2+1)…(c_m+1)\)

我们考虑先把每一个数分解质因数

用试除法会使你tle到没救，所以我们要用pollard's Rho来解决问题

（用质因数分解是因为\(10^9<2*3*5*7*11*13*17*19*23*29\)，质因数数量较少）

分解质因数后离散化，否则mle飞天

进行莫队，正常计算贡献，你交一发，会发现只有82（73），因为这个算法需要扫描每个数的每个质因子

我们很容易想到，一百（五百）以下的质数很多，而且他们作为质因子的次数也很多，所耗时间巨大

所以我们考虑将一百（五百）以下的质因数建立前缀和

这样就珂以过此题了（话说我pollard's Rho写得好丑啊）

#include <bits/stdc++.h>

#define N 100005

#define mod 19260817

#define ll long long

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Max(register int x,register int y)

{

    return x>y?x:y;

}

ll Test[10]={5,61,24251,19260817};

inline int mul(register int a,register int b,register int m)

{

    int d=((long double)a/m*b+1e-8);

    int r=a*b-d*m;

    return r<0?r+m:r;

}

inline int Pow(register int a,register int b,register int m)

{

    ll r=1;

    for(;b;b>>=1,a=mul(a,a,m))

        if(b&1)

            r=mul(r,a,m);

    return r;

}

inline bool Query(register int P)

{

    if(P==1)

        return 0;

    if(P==2||P==3||P==5||P==7)

        return 1;

    if(!(P&1)||(P%3==0)||(P%5==0)||(P%7==0))

        return 0;

    int t=P-1;

    int k=0;

    while(!(t&1))

        ++k,t>>=1;

    for(register int i=0;i<3;++i)

    {

        if(P==Test[i])

            return 1;

        int a=Pow(Test[i],t,P),nxt=a;

        for(register int j=1;j<=k;++j)

        {

            nxt=mul(nxt,nxt,P);

            if(nxt==1&&a!=1&&a!=P-1)

                return 0;

            a=nxt;

        }

        if(a!=1)

            return 0;

    }

    return 1;

}

inline int gcd(register int a,register int b)

{

    if(!a)

        return b;

    if(!b)

        return a;

    int t=__builtin_ctzll(a|b);

    a>>=__builtin_ctzll(a);

    do{

        b>>=__builtin_ctzll(b);

        if(a>b)

            a^=b^=a^=b;

        b-=a;

    }while(b!=0);

    return a<<t;

}

inline int g(register int x,register int n)

{

    int t=mul(x,x,n)+1;

    return t<n?t:t-n;

}

#define M (1<<7)-1

inline int pollardrho(register int n)

{

    ll x=(rand()%(n-1))+1,y=x,t=1,q=1;

    for(register int k=2;;k<<=1,y=x,q=1)

    {

        for(register int i=1;i<=k;++i)

        {

            x=g(x,n);

            q=mul(q,abs(x-y),n);

            if(!(i&M))

            {

                t=gcd(q,n);

                if(t>1)

                    break;

            }

        }

        if(t>1||(t=gcd(q,n))>1)

            break;

    }

    if (t==n)

    {

        t=1;

        while(t==1)

            t=gcd(abs((x=g(x, n))-y),n);

    }

    return t;

}

int f[N][105],np[N];

vector<int> v;

inline void find(register int x,register int id)

{

    if(x==1)

        return;

    if(Query(x))

    {

        f[id][++np[id]]=x;

        v.push_back(x);

        return;

    }

    int p=x;

    while(p==x)

        p=pollardrho(x);

    find(p,id);

    find(x/p,id);

}

struct query{

    int l,r,id,bl;

}q[N];

int n,m,blocksize;

inline bool cmp(register query a,register query b)

{

    return a.bl!=b.bl?a.l<b.l:((a.bl&1)?a.r<b.r:a.r>b.r);

}

int ans[N],qaq[N<<1],inv[N<<1];

int num;

inline void add(register int pos)

{

    for(register int i=1;i<=np[pos];++i)

        num=(ll)num*inv[qaq[f[pos][i]]]%mod*(qaq[f[pos][i]]+1)%mod,++qaq[f[pos][i]];

}

inline void del(register int pos)

{

    for(register int i=1;i<=np[pos];++i)

        num=(ll)num*inv[qaq[f[pos][i]]]%mod*(qaq[f[pos][i]]-1)%mod,--qaq[f[pos][i]];

}

int ispri[600],pri[600],cnt=0,sum[N][100];

inline void init()

{

    for(register int i=2;i<=500;++i)

        ispri[i]=1;

    for(register int i=2;i<=500;++i)

        if(ispri[i])

        {

            pri[ispri[i]=++cnt]=i;

            for(register int j=i<<1;j<=500;j+=i)

                ispri[j]=0;

        }

}

int main()

{

    srand(19260817);

    init();

    n=read(),m=read();

    blocksize=sqrt(n);

    inv[1]=1;

    for(register int i=2;i<=N;++i)

        inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;

    for(register int i=1;i<=n;++i)

    {

        int x=read();

        memcpy(sum[i],sum[i-1],sizeof(sum[i-1]));

        for(register int j=1;j<=cnt&&pri[j]*pri[j]<=x;++j)

            while(!(x%pri[j]))

            {

                ++sum[i][j];

                x/=pri[j];

            }

        if(x>1)

        {

            if(x<=pri[cnt])

            {

                ++sum[i][ispri[x]];

                continue;

            }

            find(x,i);

        }

    }

    sort(v.begin(),v.end());

    v.erase(unique(v.begin(),v.end()),v.end());

    for(register int i=1;i<=n;++i)

        for(register int j=1;j<=np[i];++j)

            f[i][j]=lower_bound(v.begin(),v.end(),f[i][j])-v.begin();

    for(register int i=1;i<=m;++i)

        q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].bl=(q[i].l-1)/blocksize+1;

    sort(q+1,q+1+m,cmp);

    for(register int i=0;i<n<<1;++i)

        qaq[i]=1;

    int l=1,r=0;

    num=1;

    for(register int i=1;i<=m;++i)

    {

        while(r<q[i].r)

            add(++r);

        while(l>q[i].l)

            add(--l);

        while(r>q[i].r)

            del(r--);

        while(l<q[i].l)

            del(l++);

        ans[q[i].id]=num;

        for(register int j=1;j<=cnt;++j)

            ans[q[i].id]=(ll)ans[q[i].id]*(sum[r][j]-sum[l-1][j]+1)%mod;

    }

    for(register int i=1;i<=m;++i)

        write(ans[i]),puts("");

    return 0;

}