#include #define MAXN 200007 using namespace std; fstream cinn,conn; const int bucket_sz=700; const long long mod=1e9+7; int t,n,q; long long a[MAXN]; int bucket[MAXN]; int pr[MAXN]; int br[1000007],l,r,sz; long long ans[MAXN],inv[1000007],res,invv[1000007],bro[1000007]; long long pref[MAXN]; struct query{ int l,r,id; inline friend bool operator < (query fr,query sc){ if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]sc.r; } }s[MAXN]; long long power(long long a,int b){ if(b==0)return 1; if(b==1)return a; if(b==2)return (a*a)%mod; if(b%2==0)return power(power(a,b/2),2); return (power(power(a,b/2),2)*a)%mod; } void add(int x){ if(pr[x]==0)return; br[pr[x]]++; if(br[pr[x]]==1){ res*=bro[pr[x]]; res%=mod; sz++; } } void rem(int x){ if(pr[x]==0)return; br[pr[x]]--; if(br[pr[x]]==0){ res*=invv[pr[x]]; res%=mod; sz--; } } vector primes; int del[1000007]; void eratosthen(){ for(int i=2;i<=1000000;i++){ if(del[i]==0){ primes.push_back(i); del[i]=i; } for(int f=0;f>n>>q; eratosthen(); for(int i:primes){ bro[i]=((1-i+mod)*power(i,mod-2))%mod; invv[i]=power(bro[i],mod-2); } int sum=0; pref[0]=inv[0]=1; for(int i=1;i<=n;i++){ cinn>>a[i]; int s=a[i]; while(s>1){ if(del[s/del[s]]!=del[s]){ if(del[s]>1000)pr[i]=del[s]; } s/=del[s]; } bucket[i]=i/bucket_sz; pref[i]=(pref[i-1]*a[i])%mod; inv[i]=power(pref[i],mod-2); for(int f=0;f>s[i].l>>s[i].r; s[i].id=i; } sort(s+1,s+q+1); l=1; r=0; res=1; sz=0; for(int i=1;i<=q;i++){ /*while(rs[i].l){ l--; add(l); } while(r>s[i].r){ rem(r); r--; } while(l0){ toadd*=bro[primes[f]]; toadd%=mod; ss++; } } if((ss+sz)%2==0)ans[s[i].id]=( ((res*toadd)%mod)*val )%mod; else ans[s[i].id]=(mod*mod-((res*toadd)%mod)*val)%mod; } for(int i=1;i<=q;i++){ conn<