Untitled

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
#define allam  ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
using namespace std;
typedef long long ll;

const int mod = 1e9 + 7;

const int N = 1e5 + 5, M = 1e6 + 5, sz = (int) sqrt(N);
int f[M];
int spf[M];
int fac[N], inv[N];
int a[N];
int cnt[M];
int ans = 0;

struct Query {
    int l, r, idx;

    bool operator<(Query other) {
        return make_pair(this->l / sz, this->r) < make_pair(other.l / sz, other.r);
    }
};

int modPow(int x, int b) {
    int res = 1;
    while (b) {
        if (b & 1)res = 1ll * res * x % mod;
        b >>= 1, x = 1ll * x * x % mod;
    }
    return res;
}

void init() {
    fac[0] = 1, inv[1] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = modPow(inv[i], mod - 2);
    }
    for (int i = 2; i < M; ++i) {
        if (spf[i])continue;
        for (int j = i; j < M; j += i) {
            spf[j] = i;
        }
    }
    for (int i = 1; i < M; ++i) {
        int temp = i;
        f[i] = i;
        while (temp > 1) {
            int p = spf[temp];
            while (temp % p == 0)temp /= p;
            f[i] = min(f[i], p);
        }
    }
}

void add(int idx) {
    if(f[a[idx]]==1)return;
    ans = ans + 2 * cnt[f[a[idx]]] % mod;
    cnt[f[a[idx]]]++;
}

void rem(int idx) {
    if(f[a[idx]]==1)return;
    cnt[f[a[idx]]]--;
    ans = ((ans - 2 * cnt[f[a[idx]]]) % mod + mod) % mod;
}

vector<int> go(vector<Query> q) {
    int l = q.front().l, r = q.front().l - 1;
    vector<int> ret(q.size());
    for (auto &i: q) {
        int seg = i.r - i.l + 1;
        while (l > i.l)add(--l);
        while (r < i.r)add(++r);
        while (l < i.l)rem(l++);
        while (r > i.r)rem(r--);
        ret[i.idx] = 1ll * ans * modPow(seg, mod - 2)% mod;
    }
    return ret;
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<Query> query(q);
    for (int i = 0; i < q; ++i) {
        cin >> query[i].l >> query[i].r;
        query[i].l--, query[i].r--, query[i].idx = i;
    }
    sort(query.begin(), query.end());
    for (auto &i: go(query)) {
        cout << i << '\n';
    }
}


signed main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    allam
    init();
    int _t = 1;
//    cin >> _t;
    while (_t--) {
        solve();
        if (_t) cout << "\n";
    }

}