#include using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl "\n" #define ll long long void submit(){ freopen( "coprime.in", "r", stdin ); freopen( "coprime.out", "w", stdout ); } const int MOD = 1000000007; const int MAXA = 1000000; // maximum value for a_i // Precompute smallest prime factors (spf) for factorizing numbers up to MAXA. vector spf(MAXA+1); void sieve() { for (int i = 1; i <= MAXA; i++) spf[i] = i; for (int i = 2; i * i <= MAXA; i++) { if (spf[i] == i) { // i is prime for (int j = i*i; j <= MAXA; j += i) { if (spf[j] == j) spf[j] = i; } } } } // Compute modular exponentiation (and hence modular inverse for primes). long long modexp(long long base, long long exp) { long long res = 1; while(exp) { if(exp & 1) res = (res * base) % MOD; base = (base * base) % MOD; exp >>= 1; } return res; } long long modinv(long long x) { return modexp(x, MOD-2); } // Function to factorize x into its distinct primes using spf. vector getDistinctPrimes(int x) { vector primes; while (x > 1) { int p = spf[x]; primes.push_back(p); while(x % p == 0) x /= p; } return primes; } // Segment Tree for product queries struct SegTree { int n; vector tree; SegTree(int n) : n(n) { tree.assign(4*n, 1); } void update(int idx, int pos, long long val, int l, int r) { if(l == r) { tree[idx] = (tree[idx] * val) % MOD; return; } int mid = (l+r)/2; if(pos <= mid) update(2*idx, pos, val, l, mid); else update(2*idx+1, pos, val, mid+1, r); tree[idx] = (tree[2*idx] * tree[2*idx+1]) % MOD; } long long query(int idx, int ql, int qr, int l, int r) { if(ql > r || qr < l) return 1; if(ql <= l && r <= qr) return tree[idx]; int mid = (l+r)/2; long long leftVal = query(2*idx, ql, qr, l, mid); long long rightVal = query(2*idx+1, ql, qr, mid+1, r); return (leftVal * rightVal) % MOD; } }; int main(){ submit(); ios::sync_with_stdio(false); cin.tie(nullptr); sieve(); int N, Q; cin >> N >> Q; vector a(N+1); for (int i = 1; i <= N; i++) { cin >> a[i]; } // Precompute prefix products: prefix[i] = a1*a2*...*a[i] mod MOD. vector prefix(N+1, 1); for (int i = 1; i <= N; i++){ prefix[i] = (prefix[i-1] * a[i]) % MOD; } // Prepare the segment tree; initial value at each index is 1. SegTree seg(N); // lastOccurrence[p] stores the last index where prime p was processed. vector lastOccurrence(MAXA+1, 0); // We'll process queries offline sorted by r. struct Query { int l, r, idx; }; vector queries(Q); for (int i = 0; i < Q; i++){ cin >> queries[i].l >> queries[i].r; queries[i].idx = i; } sort(queries.begin(), queries.end(), [](const Query &q1, const Query &q2){ return q1.r < q2.r; }); // To store the final answers. vector ans(Q); // Process array positions and answer queries as r increases. int currentR = 0; for(auto &q : queries){ while(currentR < q.r) { currentR++; // Factorize a[currentR] into its distinct prime factors. vector primes = getDistinctPrimes(a[currentR]); // For each prime factor p in a[currentR]: for (int p : primes) { // f(p) = (p-1)/p mod MOD. long long fp = ((p - 1LL) * modinv(p)) % MOD; // If p has been seen before, remove its contribution from the old index. if(lastOccurrence[p] != 0) { seg.update(1, lastOccurrence[p], modinv(fp), 1, N); } // Add contribution at the current index. seg.update(1, currentR, fp, 1, N); lastOccurrence[p] = currentR; } } // For query [l, r]: long long P = (prefix[q.r] * modinv(prefix[q.l - 1])) % MOD; long long F = seg.query(1, q.l, q.r, 1, N); ans[q.idx] = (P * F) % MOD; } // Output the answers in the original order. for (long long res : ans) cout << res << "\n"; return 0; }