#include using namespace std; typedef long long ll; const int MOD = 1000000007; const int MAXVAL = 1000000; // Compute smallest prime factor for each number up to n. vector compute_spf(int n) { vector spf(n+1); for (int i = 1; i <= n; i++) { spf[i] = i; } for (int i = 2; i * i <= n; i++) { if (spf[i] == i) { for (int j = i * i; j <= n; j += i) { if (spf[j] == j) spf[j] = i; } } } return spf; } // Compute modular inverses for 1..n modulo MOD. vector compute_inverses(int n) { vector inv(n+1); inv[1] = 1; for (int i = 2; i <= n; i++){ inv[i] = (ll)(MOD - MOD / i) * inv[MOD % i] % MOD; } return inv; } // Fast modular exponentiation. ll modexp(ll base, ll exp, ll mod) { ll res = 1 % mod; base %= mod; while(exp){ if(exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } // Fenwick tree (Binary Indexed Tree) for product queries. struct Fenw { int n; vector fenw; Fenw(int n) : n(n), fenw(n+1, 1) { } // Multiply position i (1-indexed) by mult. void update(int i, ll mult) { for(; i <= n; i += i & -i) fenw[i] = (fenw[i] * mult) % MOD; } // Query product from 1 to i. ll query(int i) { ll res = 1; for(; i > 0; i -= i & -i) res = (res * fenw[i]) % MOD; return res; } // Range query product in [l, r] (1-indexed). ll range_query(int l, int r) { ll prod_r = query(r); ll prod_lm1 = query(l - 1); ll invProd = modexp(prod_lm1, MOD - 2, MOD); return (prod_r * invProd) % MOD; } }; // Query structure. struct Query { int l, r, idx; }; // Main function. int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ifstream fin("coprime.in"); ofstream fout("coprime.out"); if(!fin || !fout){ cerr << "Error opening files!" << endl; return 1; } int N, Q; fin >> N >> Q; vector arr(N); for (int i = 0; i < N; i++){ fin >> arr[i]; } // Precompute prefix products (mod MOD) and count of ones. vector preProd(N+1, 1); vector prefixOnes(N+1, 0); for (int i = 0; i < N; i++){ preProd[i+1] = (preProd[i] * arr[i]) % MOD; prefixOnes[i+1] = prefixOnes[i] + (arr[i] == 1); } // Precompute SPF and modular inverses up to MAXVAL. vector spf = compute_spf(MAXVAL); vector inv = compute_inverses(MAXVAL); // Precompute distinct prime factors for each a[i]. vector> factors(N); for (int i = 0; i < N; i++){ int x = arr[i]; if(x == 1) continue; int prev = 0; while(x > 1){ int p = spf[x]; if(p != prev) { factors[i].push_back(p); prev = p; } while(x % p == 0) x /= p; } } // Read queries (convert to 0-indexed) and sort them by r. vector queries(Q); for (int i = 0; i < Q; i++){ int l, r; fin >> l >> r; l--; r--; // convert to 0-index queries[i] = {l, r, i}; } sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) { return a.r < b.r; }); // We'll use a Fenwick tree to maintain the product of contributions from // distinct primes. For each prime p, we want to contribute f(p) = (p-1)/p // exactly once at its latest occurrence. Fenw fenw(N); // lastOccurrence[p] will store the most recent index where prime p appeared. vector lastOccurrence(MAXVAL+1, -1); vector answer(Q, 0); int curR = -1; int qi = 0; // Process indices in increasing order (simulate r pointer). while(qi < Q){ int targetR = queries[qi].r; while(curR < targetR){ curR++; // For each prime factor in a[curR], update its contribution. for (int p : factors[curR]){ // If p has occurred before, remove its old contribution. if(lastOccurrence[p] != -1){ // The old contribution was f(p) = (p-1)*inv[p]. // Its inverse is p*inv[p-1] (since (p-1)/p inverted is p/(p-1)). ll removal = ((ll)p * inv[p - 1]) % MOD; fenw.update(lastOccurrence[p] + 1, removal); } // Now add contribution at curR. ll addFactor = ((ll)(p - 1) * inv[p]) % MOD; fenw.update(curR + 1, addFactor); lastOccurrence[p] = curR; } } // Now answer all queries with r == targetR. while(qi < Q && queries[qi].r == targetR){ int l = queries[qi].l, r = queries[qi].r; // totient multiplier is product of contributions for primes whose last occurrence is in [l, r]. ll totientPart = fenw.range_query(l + 1, r + 1); // Product over [l, r] computed using prefix products. ll prod = (preProd[r + 1] * modexp(preProd[l], MOD - 2, MOD)) % MOD; // If the entire segment consists only of ones, then the product is 1 and // there is no representation (a+b=1 has no solution in positive integers). if(prefixOnes[r + 1] - prefixOnes[l] == (r - l + 1)) answer[queries[qi].idx] = 0; else answer[queries[qi].idx] = (prod * totientPart) % MOD; qi++; } } // Output answers in the original order. for (int i = 0; i < Q; i++){ fout << answer[i] << "\n"; } fin.close(); fout.close(); return 0; }