#include #include #include #include #include #include #include #include #include using namespace std; ifstream cin("coprime.in"); ofstream cout("coprime.out"); #define M 1000000007 vector factoriz[1000005]; long long a[200005]; unordered_map mp; int totient[1000005]; long long invers[1000005]; void euclid(long long a, long long b , long long &x, long long &y) { if(b==0) { x=1; y=0; } else { long long c=a/b; long long x1,y1; euclid (b, a%b, x1, y1); x=y1; y=x1-c*y1; } } int main() { long long maxim=1000000; int n,q; cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i]; maxim=max(maxim,a[i]); } for(int i=2;i<=maxim;i++) totient[i]=i; for(int i=2;i<=maxim;i++) if(totient[i]==i) { totient[i]--; long long x,y; euclid(i,M,x,y); while(x<0) x+=M; invers[i]=x; factoriz[i].push_back(i); for(int j=2*i;j<=maxim;j+=i) { factoriz[j].push_back(i); totient[j]=totient[j]/i*(i-1); } } while(q--) { int l,r; cin>>l>>r; mp.clear(); long long rez=1; for(int i=l;i<=r;i++) { rez=(rez*a[i])%M; for(auto j:factoriz[a[i]]) { if(!mp[j]) { rez=(rez*(j-1))%M; rez=(rez*invers[j])%M; } mp[j]=1; } } cout<