#include using namespace std; const int N = 1000001; vector lp(N+1); vector pr; long long ans[100001]; unordered_map>indices; //dequeindices[1000001]; const long long mod=1e9+7; const int k=(1<<18); long long st[2*k+1]; void upd(int ind, int val) { ind+=k; st[ind]=val; ind/=2; while(ind>0) { st[ind]=st[ind*2]*st[ind*2+1]; st[ind]%=mod; ind/=2; } } long long ask(int from, int to, int cur=1, int l=0, int r=k-1) { if(tor)return 1; if(from<=l && r<=to)return st[cur]; int mid=(l+r)/2; return (ask(from,to,cur*2,l,mid)*ask(from,to,cur*2+1,mid+1,r))%mod; } vectorget_primes(int num) { vectorprim; if(num<=1)return prim; while(num!=1) { if(prim.size()==0 || prim.back()!=lp[num]) { prim.push_back(lp[num]); } num/=lp[num]; } return prim; } int a[200001]; void solve() { int n,q;cin>>n>>q; for(int i=0;i>a[i]; for(int i=0;iprim=get_primes(a[i]); for(int prime:prim) { indices[prime].push_back(i); if(indices[prime].size()==1) { int num=st[k+i]; num/=prime; num*=(prime-1); upd(i, num); } } } vector,int>>v; for(int i=0;i>x>>y; x--;y--; v.push_back({{x,y},i}); } sort(v.begin(),v.end()); int cur=0; for(int i=0;iprim = get_primes(a[cur]); for(int prime:prim) { indices[prime].pop_front(); if(indices[prime].size()>0) { int new_ind=indices[prime].front(); int num=st[k+new_ind]; num/=prime; num*=(prime-1); upd(new_ind, num); } } } ans[ind]=ask(l, r); } for(int i=0;i