// we both did the best we could do, underneath the same moon, in different galaxies #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#define int long long typedef long long ll; typedef long double ld; using namespace std; const int mod = 1e9 + 7; void upd(int& a, int b) { a = (a + b) % mod; } int add(int a, int b) { return (a + b) % mod; } int mul(int a, int b) { return (a * 1ll * b) % mod; } int pwr(int a, int b = mod - 2) { if (!b) return 1; int h = pwr(a, b >> 1); h = mul(h, h); if (b & 1) h = mul(h, a); return h; } const int maxn = 1e6 + 5; vector st; void upds(int i, int x) { for (i += maxn; i > 0; i >>= 1) st[i] = mul(st[i], x); } int query(int l, int r) { int ans = 1; for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) ans = mul(ans, st[l++]); if (r & 1) ans = mul(ans, st[--r]); } return ans; } struct ques { int l, r, i; }; vector ans; int main() { ios::sync_with_stdio(false); cin.tie(0); st.assign(maxn * 2, 1); vector > pr(maxn); for (int i = 2; i < maxn; i++) { if (pr[i].empty()) { for (int j = i; j < maxn; j += i) pr[j].push_back(i); } } ifstream cin("coprime.in"); ofstream cout("coprime.out"); int n, q; cin >> n >> q; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; ans.assign(q, 0); vector > qu(n); for (int i = 0; i < q; i++) { ques qi; cin >> qi.l >> qi.r; qi.l--, qi.r--, qi.i = i; qu[qi.r].push_back(qi); } vector lst(maxn, -1); for (int r = 0; r < n; r++) { upds(r, a[r]); for (int p : pr[a[r]]) { int e = add(1, mod - pwr(p)); upds(r, e); if (lst[p] != -1) upds(lst[p], pwr(e)); lst[p] = r; } for (ques qi : qu[r]) { ans[qi.i] = query(qi.l, qi.r); } } for (int i = 0; i < q; i++) cout << ans[i] << "\n"; return 0; }