inghetata

#include <fstream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;
ifstream fin("inghetata.in");
ofstream fout("inghetata.out");

const int MAXN = 200005;
long long fct[MAXN], inv[MAXN];

long long power(long long a, long long b) {
    long long r = 1; a %= MOD;
    while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
    return r;
}
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fct[n] * inv[k] % MOD * inv[n - k] % MOD;
}

int main() {
    int C, N;
    fin >> C >> N;
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) fin >> A[i];

    vector<int> L(N + 1), R(N + 1), G(N + 1);
    for (int i = 1; i <= N; i++) {        // extindere stânga cu salturi
        L[i] = i; int cur = i - 1;
        while (cur >= 1 && A[i] % A[cur] == 0) { L[i] = L[cur]; cur = L[cur] - 1; }
    }
    for (int i = N; i >= 1; i--) {        // extindere dreapta cu salturi
        R[i] = i; int cur = i + 1;
        while (cur <= N && A[i] % A[cur] == 0) { R[i] = R[cur]; cur = R[cur] + 1; }
    }
    for (int i = 1; i <= N; i++) G[i] = R[i] - L[i] + 1;

    if (C == 1) {
        int best = 1;
        for (int i = 2; i <= N; i++) if (G[i] > G[best]) best = i;
        fout << best << "\n";
    } else {
        fct[0] = 1;
        for (int i = 1; i <= N; i++) fct[i] = fct[i - 1] * i % MOD;
        inv[N] = power(fct[N], MOD - 2);
        for (int i = N; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;

        int Q; fin >> Q;
        while (Q--) {
            int i, st, dr; fin >> i >> st >> dr;
            int n = G[i];
            long long s = 0;
            for (int k = st; k <= dr; k++) s = (s + comb(n - 1, k - 1)) % MOD; // C(n-1,k-1)
            fout << s << "\n";
        }
    }
    return 0;
}