#include # define clr(x,a) memset(x,a,sizeof(x)) # define all(a) a.begin(), a.end() # define deb(x) cout<<#x<<"=="<>t; while(t--) # define rev(s) reverse(s.begin(),s.end()) # define linija cout<<"___________\n"; using namespace std; typedef long long ll; typedef vector vi; typedef pair pii; const int mxN=1000006, mxM=5005, LOG=25, inf = 2e9; const long long mod=1e9+7; template T nzd(T a, T b){if(b==0) return a;else return nzd(b, a%b);} template T nzs(T a, T b){return(a*(b/nzd(a,b)));} template T stepenuj(T e, T n){T x=1,p=e;while(n){if(n&1)x=(x*p)%mod;p=(p*p)%mod;n>>=1;}return x;} template inline T na2(T x){return x*x;} using namespace std; const int MXBUFFer = 64009000; const int MAX_N = 1000006; // Adjust based on the problem constraints vector spf(MAX_N); // Smallest prime factor (SPF) vector>> segTree(4 * MAX_N); // Segment tree for prime factorization int n, a[mxN], q, l, r; vector> factors; // Global variable for storing factors char *pos, BUFFER[MXBUFFer]; ///fread char buffer ll res; inline int getint(){ char C; while ((C = *pos++) < '0'); int RET = C -= '0'; while ((C = *pos++) >= '0') RET = 10 * RET + C - '0'; return RET; } void sieve() { for (int i = 2; i < MAX_N; i++) spf[i] = i; for (int i = 2; i * i < MAX_N; i++) { if (spf[i] == i) { for (int j = i * i; j < MAX_N; j += i) { if (spf[j] == j) spf[j] = i; } } } } vector factorize(int n) { vector result; while (n > 1) { int prime = spf[n]; int cmt = 0; while (n % prime == 0) { n /= prime; cmt++; } result.push_back({prime, cmt}); } return result; } void build(int node, int start, int end) { if (start == end) { segTree[node] = factorize(a[start]); } else { int mid = (start + end) / 2; build(2 * node, start, mid); build(2 * node + 1, mid + 1, end); // Merge two sorted lists in O(K) vector> &left = segTree[2 * node]; vector> &right = segTree[2 * node + 1]; vector> &cur = segTree[node]; int i = 0, j = 0; while (i < left.size() && j < right.size()) { if (left[i].first == right[j].first) { cur.emplace_back(left[i].first, left[i].second + right[j].second); i++; j++; } else if (left[i].first < right[j].first) { cur.push_back(left[i++]); } else { cur.push_back(right[j++]); } } while (i < left.size()) cur.push_back(left[i++]); while (j < right.size()) cur.push_back(right[j++]); } } // **4. Query in O(log N * K)** vector> query(int node, int start, int end, int l, int r) { if (r < start || l > end) return {}; // Out of range if (l <= start && end <= r) return segTree[node]; // Fully inside range int mid = (start + end) / 2; vector> left = query(2 * node, start, mid, l, r); vector> right = query(2 * node + 1, mid + 1, end, l, r); // Merge results efficiently vector> result; int i = 0, j = 0; while (i < left.size() && j < right.size()) { if (left[i].first == right[j].first) { result.emplace_back(left[i].first, left[i].second + right[j].second); i++; j++; } else if (left[i].first < right[j].first) { result.push_back(left[i++]); } else { result.push_back(right[j++]); } } while (i < left.size()) result.push_back(left[i++]); while (j < right.size()) result.push_back(right[j++]); return result; } ll euler_totient() { ll n = 1, phi = 1, ostalo; for (pii factor : factors) { ll prime = factor.first; ll exponent = factor.second; n = (n*stepenuj(prime, exponent))%mod; ostalo = (stepenuj(prime, exponent) - stepenuj(prime, exponent - 1) + mod)%mod; phi = (phi * ostalo)%mod; } return phi; } void calc(){ factors = query(1, 0, n - 1, l-1, r-1); res = euler_totient(); pr("%lld\n", res); } int main() { sieve(); // Precompute SPF freopen("coprime.in", "r", stdin); fread(pos = BUFFER, 1, MXBUFFer, stdin); n = getint(); q = getint(); for(int i = 0; i < n; i++){ a[i] = getint(); } build(1, 0, n - 1); freopen("coprime.out", "w", stdout); while(q--){ l = getint(); r = getint(); calc(); } return 0; }