题目链接：http://www.ifrog.cc/acm/problem/1153

题意：给你一个序列$a$，每次查询一个区间$[l,r]$的乘积的约数个数$\bmod 19260817$

思路：官方题解：对每个数进行质因子分解，考虑一个数的约数个数即为其每个质因子出现次数$+1$的乘积，所以维护这个即可。考虑每个数只有一个大于$1000$的质数，对这部分用根号分治。对于小于$1000$的质因子（只有$168$个），维护一个前缀和$pre[i][j]$表示第$i$个质因子在前$j$个数中出现次数,对于大于$1000$的质因子，用莫队维护即可。

反思：比赛的时候只想到了预处理前缀和后就没继续想了。。觉得肯定要$T$。。。观察力还不够啊，每个数只有一个大于$1000$的质数这个性质可以直接用莫队来维护觉得挺神奇的，收获挺大。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int maxm=1000+5;
const int INF=0x3f3f3f3f;
const int P=19260817;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,m,res=1,block[maxn],a[maxn],inv[maxn],ans[maxn],prime[maxm],num[maxm*maxm],pre[170][maxn];
bool isPrime[maxm];
struct Query{
    int l,r,id;
    bool operator<(const Query&a)const{
        if (block[l]==block[a.l]) return r<a.r;
        return block[l]<block[a.l];
    }
}q[maxn];
void inc(int x){
    if(num[x]!=1) res=res*1LL*inv[num[x]]%P;
    res=res*1LL*(++num[x])%P;
}
void ins(int x){
    if (a[x]!=1) inc(a[x]);
}
void dec(int x){
    res=res*1LL*inv[num[x]--]%P;
    if (num[x]!=1) res=res*1LL*num[x]%P;
}
void des(int x){
    if (a[x]!=1) dec(a[x]);
}
int ksm(int a,int n){
    int res=1;
    while (n){
        if (n&1) res=(1LL*res*a)%P;
        a=(1LL*a*a)%P;
        n>>=1;
    }
    return res;
}
void init(){
    for (int i=2;i<=1000;i++){
        if (!isPrime[i]) prime[++prime[0]]=i;
        for (int j=1;i*prime[j]<=1000 && j<=prime[0];j++){
            isPrime[i*prime[j]]=true;
            if (i%prime[j]==0) break;
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=prime[0];j++){
            while (a[i]%prime[j]==0){
                a[i]/=prime[j];
                pre[j][i]++;
            }
        }
    }
    for (int i=1;i<=1000000;i++) num[i]=1;
    for (int j=1;j<=prime[0];j++){
        for (int i=1;i<=n;i++){
            pre[j][i]+=pre[j][i-1];
        }
    }
    for (int i=1;i<=n+1;i++) inv[i]=ksm(i,P-2);
}
int main(){
    read(n),read(m);
    for (int i=1;i<=n;i++) read(a[i]);
    init();
  //  int limit=n/sqrt(m/3);
    int limit=(int)sqrt(n+0.5);
    for (int i=1;i<=n;i++) block[i]=(i-1)/limit;
    for (int i=1;i<=m;i++){
        read(q[i].l),read(q[i].r),q[i].id=i,ans[i]=1;
        int tmp;
        for (int j=1;j<=prime[0];j++)if (tmp=pre[j][q[i].r]-pre[j][q[i].l-1])
            ans[i]=ans[i]*1LL*(tmp+1)%P;
    }
    sort(q+1,q+1+m);
    for (int i=1,l=1,r=0;i<=m;i++){
        while (l>q[i].l) ins(--l);
        while (r<q[i].r) ins(++r);
        while (l<q[i].l) des(l++);
        while (r>q[i].r) des(r--);
        ans[q[i].id]=ans[q[i].id]*1LL*res%P;
    }
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}