d.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 10;
ll inv[2000000];
int cnt[MAXN], min_div[MAXN], a[MAXN], ans[MAXN];
pair <pair <int, int>, pair <int, int> > b[MAXN];
ll answer = 1;
ll bin_power(ll x, ll y){
    if (y == 0)
        return 1;
    if (y & 1){
        return x * bin_power(x, y - 1) % MOD;
    }
    else{
        ll z = bin_power(x, y >> 1);
        return (z * z) % MOD;
    }
}

void add(int x){
    while (x > 1){
        answer *= inv[cnt[min_div[x]] + 1];
        answer %= MOD;
        cnt[min_div[x]]++;
        answer *= (cnt[min_div[x]] + 1);
        answer %= MOD;
        x /= min_div[x];
    }
}

void del(int x){
    while (x > 1){
        answer *= inv[cnt[min_div[x]] + 1];
        answer %= MOD;
        cnt[min_div[x]]--;
        answer *= (cnt[min_div[x]] + 1);
        answer %= MOD;
        x /= min_div[x];
    }
}

void solve(){
    for (int i = 2; i <= 10000; i++){
        if (min_div[i] == 0){
            min_div[i] = i;
            for (int j = i * i; j <= 10000; j += i){
                if (min_div[j] == 0)
                    min_div[j] = i;
            }
        }
    }

    for (int i = 0; i < 2000000; i++){
        inv[i] = bin_power(i, MOD - 2);
    }
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int len = sqrt(n);
    for (int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        b[i].f.f = l / len;
        b[i].f.s = r;
        b[i].s.f = l;
        b[i].s.s = i;
    }

    sort (b + 1, b + q + 1);
    int l = 1;
    int r = 0;

    for (int i = 1; i <= q; i++){
        while (r < b[i].f.s){
            r++;
            add(a[r]);
        }
        while (l > b[i].s.f){
            l--;
            add(a[l]);
        }
        while (r > b[i].f.s){
            del(a[r]);
            r--;
        }
        while (l < b[i].s.f){
            del(a[l]);
            l++;
        }
        ans[b[i].s.s] = answer;
    }

    for (int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
    }
}

int main() {

    IOS;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}