#pragma GCC optimize("O3") #include #define endl '\n' using namespace std; const int MAXA = 1e6; const int MAXN = 2e5; const int64_t MOD = 1e9+7; int N, Q; int64_t arr[MAXN+50]; int64_t phi[MAXA+50]; void PrecomputeEulerFunction() { for (int i = 1; i <= MAXA; i++) { phi[i] = i; } for (int i = 2; i <= MAXA; i++) { if (phi[i] == i) { for (int j = i; j <= MAXA; j += i) { phi[j] -= (phi[j]/i); } } } } int64_t DIVIDE(int64_t base, int64_t pow) { int64_t res = 1; while (pow != 0) { if (pow&1) res = (res*base)%MOD; base = (base*base)%MOD; pow >>= 1; } return res; } class SegmentTree { private: int N; int64_t treePHI[MAXN*4]; int64_t tree[MAXN*4]; void Recalculate(int node) { tree[node] = (tree[node*2]*tree[node*2+1])%(MAXA+1); treePHI[node] = (treePHI[node*2]*treePHI[node*2+1])%MOD; int64_t gcd = __gcd(tree[node*2], tree[node*2+1])%(MAXA+1); treePHI[node] = (treePHI[node]*gcd)%MOD; treePHI[node] = (treePHI[node]*DIVIDE(phi[gcd], MOD-2)); } void BuildInternal(const int64_t *arr, int node, int L, int R) { if (L == R) { //cout << arr[L] << " ---- " << phi[arr[L]] << endl; treePHI[node] = phi[arr[L]]; tree[node] = arr[L]; return; } this->BuildInternal(arr, node*2, L, (L+R)/2); this->BuildInternal(arr, node*2+1, (L+R)/2+1, R); this->Recalculate(node); } pair QueryInternalPHI(const int queryL, const int queryR, int node, int L, int R) { if (queryL <= L && R <= queryR) return {treePHI[node], tree[node]}; if (L > queryR || R < queryL) return {1, 1}; pair ansL = QueryInternalPHI(queryL, queryR, node*2, L, (L+R)/2); pair ansR = QueryInternalPHI(queryL, queryR, node*2+1, (L+R)/2+1, R); int64_t gcd = __gcd(ansL.second, ansR.second)%(MAXA+1); pair ans = {((((ansL.first*ansR.first)%MOD*gcd)%MOD)*DIVIDE(phi[gcd], MOD-2))%MOD, (ansL.second*ansR.second)%(MAXA+1)}; return ans; } public: SegmentTree(int N) { this->N = N; } void Build(int64_t *arr) { BuildInternal(arr, 1, 0, N-1); } int64_t Query(int queryL, int queryR) { int64_t phiAns = QueryInternalPHI(queryL, queryR, 1, 0, N-1).first%MOD; return phiAns;//(((phiAns*gcdAns)%MOD)*DIVIDE(phi[int(gcdAns)], MOD-2))%MOD; } }; int main() { #ifndef __LOCAL__ freopen("coprime.in", "r", stdin); freopen("coprime.out", "w", stdout); #endif // __LOCAL__ PrecomputeEulerFunction(); cin >> N >> Q; for (int i = 0; i < N; i++) { cin >> arr[i]; //cout << "Phi(" << arr[i] << ") = " << phi[arr[i]] << endl; } SegmentTree *tree = new SegmentTree(N); tree->Build(arr); for (int i = 0; i < Q; i++) { int l, r; cin >> l >> r; cout << tree->Query(l-1, r-1) << endl; } return 0; }