此题能否开放下载数据功能

#include<bits/stdc++.h>
#define il inline
#define int long long
#define ll long long
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&-(x))
#define pii pair<int,int> 
#define mk make_pair
using namespace std;
const int N=5e5+5,mod=1e9+7;
il int M(int x){
    if(x>=mod) return x%mod;
    return x%mod;
}
il int qpow(ll x,int b){
    ll res=1;
    while(b){
        if(b&1) res=res*x%mod;
        x=x*x%mod;b>>=1;
    }
    return res;
}
int n,m,T=1;
int pri[N],to[N],cnt,rev[N];
bool p[N];
ll fac[N<<1],inv[N<<1];
il int C(int n,int m){
    if(n<m||m<0) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
il void init(int n){
    fac[0]=1;
    for(int i=1;i<=n*2;i++) fac[i]=fac[i-1]*i%mod;
    inv[n*2]=qpow(fac[n*2],mod-2);
    for(int i=n*2-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    to[1]=1;
    for(int i=2;i<=n;i++) {
        if(!p[i]) pri[++cnt]=i,to[i]=1,rev[i]=cnt;
        for(int j=1;j<=cnt&&1ll*i*pri[j]<=n;j++) {
            p[i*pri[j]]=1;
            to[i*pri[j]]=i;
            if(i%pri[j]==0) break;
        }
    }
}
int a[N],lst[N],L[N];
vector<pii> pr[N],h[N];
vector<pii> q[N];
int ans[N];
il int calc(int i,int len){
    ll res=1;
    for(pii now:h[i]) {
        res=res*C(len+now.second,now.second)%mod;
    }
    return res;
}
il int Calc(int x,int y,int len){
    // return 0;
    if(!len) return 1;
    ll res=1;
    while(x!=1||y!=1) {
        int k;
        if(x==1) k=y/to[y];
        else if(y==1) k=x/to[x];
        else k=min(x/to[x],y/to[y]);
        int c1=0,c2=0;
        while(x%k==0) x/=k,c1++;
        while(y%k==0) y/=k,c2++;
        res=res*C(abs(c1-c2)+len,len)%mod;
    }
    return res;
}

struct matrix{
    int a[2][2];
    // matrix (){
    //     a[0][0]=a[1][1]=a[0][1]=a[1][0]=0;
    // }
    il void id(){
        a[0][0]=a[1][1]=1;a[0][1]=a[1][0]=0;
    }
    il void init(int A,int B,int C,int D){
        a[0][0]=A,a[0][1]=B,a[1][0]=C,a[1][1]=D;
    }
    friend matrix operator *(matrix x,matrix y){
        matrix ans;
        ans.init(0,0,0,0);
        for(int i=0;i<2;i++)
            for(int k=0;k<2;k++)
                for(int j=0;j<2;j++) 
                    (ans.a[i][j]+=x.a[i][k]*y.a[k][j])%=mod; 

        // ans.a[0][0]=(1ll*x.a[0][0]*y.a[0][0]+1ll*x.a[0][1]*y.a[1][0])%mod;
        // ans.a[0][1]=(1ll*x.a[0][0]*y.a[0][1]+1ll*x.a[0][1]*y.a[1][1])%mod;
        // ans.a[1][0]=(1ll*x.a[1][0]*y.a[0][0]+1ll*x.a[1][1]*y.a[1][0])%mod;
        // ans.a[1][1]=(1ll*x.a[1][0]*y.a[0][1]+1ll*x.a[1][1]*y.a[1][1])%mod;
        return ans;
    }
    friend matrix operator +(matrix x,matrix y){
        matrix ans;
        ans.a[0][0]=M(x.a[0][0]+y.a[0][0]);
        ans.a[0][1]=M(x.a[0][1]+y.a[0][1]);
        ans.a[1][0]=M(x.a[1][0]+y.a[1][0]);
        ans.a[1][1]=M(x.a[1][1]+y.a[1][1]);
        return ans;
    }
    il bool emp(){
        if(a[0][0]&&a[1][1]&&(!a[1][0])&&(!a[0][1])) return 1;
        return 0;
    }
};
struct sgt{
    struct node{
        matrix sum,tag;
    }t[N<<2];
    il void build(int x,int l,int r){
        t[x].tag.id();
        if(l==r) return ;
        build(ls(x),l,mid);build(rs(x),mid+1,r);
    }
    il void pushup(int x){
        t[x].sum=t[ls(x)].sum+t[rs(x)].sum;
    }
    il void spread(int x,matrix sum){
        t[x].tag=sum*t[x].tag;
        t[x].sum=sum*t[x].sum;
    }
    il void pushdown(int x){
        if(!t[x].tag.emp()){
            // cerr<<t[x].tag.a[0][0]<<' '<<t[x].tag.a[0][1]<<' '<<t[x].tag.a[1][0]<<' '<<t[x].tag.a[1][1]<<'\n';
            spread(ls(x),t[x].tag);
            spread(rs(x),t[x].tag);
            t[x].tag.id();
        }
        // else T++;
    }
    il void change(int x,int l,int r,int p) {
        if(l==r) {
            t[x].sum.init(1,0,0,0);
            return;
        }
        pushdown(x);
        if(p<=mid) change(ls(x),l,mid,p);
        else change(rs(x),mid+1,r,p);
        pushup(x);
    }  
    il void mul(int x,int l,int r,int L,int R,matrix sum){
        if(l>=L&&r<=R) {
            spread(x,sum);
            return;
        }
        pushdown(x);
        if(L<=mid) mul(ls(x),l,mid,L,R,sum);
        if(R>mid) mul(rs(x),mid+1,r,L,R,sum);
        pushup(x);
    }
    il int query(int x,int l,int r,int L,int R){
        if(l>=L&&r<=R) return t[x].sum.a[1][0];        
        pushdown(x);
        int res=0;
        if(L<=mid) res+=query(ls(x),l,mid,L,R);
        if(R>mid) res+=query(rs(x),mid+1,r,L,R);
        return M(res);
    }
}t1;

// int f[N],g[N];
il void mul(int l,int r,int sum,bool op){
    matrix k;
    k.init(sum,0,sum*op,1);
    if(l<=r)
    t1.mul(1,1,n,l,r,k);
    // for(int i=l;i<=r;i++) {
    //     f[i]=f[i]*sum%mod;
    // }

}
il void change(int p,int sum){
    // f[p]=sum;
    t1.change(1,1,n,p);
}
il int Query(int l,int r){
    // int res=0;
    // for(int i=l;i<=r;i++) res+=g[i];
    // return res%mod;
    return t1.query(1,1,n,l,r);
}
signed main(){
    init(N-1);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    L[0]=1;
    for(int i=1;i<=n;i++) {
        int x=a[i];
        L[i]=L[i-1];
        lst[i]=(a[i-1]==1ll?lst[i-1]:i-1);
        // cerr<<"i:" <<i<<' '<<lst[i]<<'\n';
        if(a[i]>1){
            while(x>1) {
                int y=x/to[x],c=0;
                while(x%y==0) x/=y,c++;
                h[i].push_back({y,c});
                if(pr[rev[y]].size()>1) {
                    int r=pr[rev[y]].size()-1,k=pr[rev[y]][r].second;
                    if(k<c) {
                        if(pr[rev[y]][r-1].second>k) L[i]=max(L[i],pr[rev[y]][r-1].first+1);
                    }
                }  
                if(pr[rev[y]].size()>0) {

                    pii now=pr[rev[y]][pr[rev[y]].size()-1];
                    if(now.first<lst[i]) L[i]=max(L[i],now.first+1);
                    if(now.second==c) pr[rev[y]][pr[rev[y]].size()-1]={i,c};
                    else pr[rev[y]].push_back({i,c});
                }
                else pr[rev[y]].push_back({i,c});
            } 
        }
        
    }
    // for(int i=1;i<=n;i++) cerr<<L[i]<<' ';cerr<<'\n';
    for(int i=1;i<=m;i++) {
        int l,r;
        cin>>l>>r;
        q[r].push_back({l,i});
    }
    t1.build(1,1,n);
    for(int i=1;i<=n;i++) {
        int l=lst[i];
        change(i,1);
        mul(1,L[i]-1,0,1);
        if(a[i]==1) {
            mul(lst[i]+1,i,1,1);
            if(lst[i])
            mul(L[i],lst[i],calc(lst[i],i-lst[i]),1);
        }
        else {
            mul(i,i,1,1);
            for(int j=lst[i]+1;j<i;j++) {
                mul(j,j,calc(i,i-j),1);
            }
            if(lst[i])
            mul(L[i],lst[i],Calc(a[i],a[lst[i]],i-1-lst[i]),1);
        }
        // for(int j=1;j<=n;j++) g[j]=(g[j]+f[j])%mod;
        // for(int j=1;j<=n;j++) cerr<<f[j]<<' ';cerr<<'\n';
        for(pii now:q[i]) {
            ans[now.second]=Query(now.first,i);
        }
        if(a[i]==1) {
            if(lst[i]) {
                int Inv=qpow(calc(lst[i],i-lst[i]),mod-2);
                mul(L[i],lst[i],Inv,0);
            }
        } 

    }
    for(int i=1;i<=m;i++)  cout<<ans[i]<<'\n'; 
    // cerr<<T<<'\n';
    return 0;

}
/*
1 0 0 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 0 
3 2 1 0 0 0 0 0 0 0 
6 4 2 1 0 0 0 0 0 0 ----22
18 12 6 1 1 0 0 0 0 0 ----42
54 36 18 9 4 1 0 0 0 0 
216 144 72 36 16 4 1 0 0 0 
432 288 144 72 32 8 2 1 0 0 
432 288 144 72 32 8 2 1 1 0 
864 576 288 144 64 16 4 2 2 1 
g++ P_14523_MX_S_11_T_4_Ice_Drop.cpp -o 1
./1 <icedrop4.in> 1.out
diff 1.out icedrop4.ans -Z
*/