#include <cstdio>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;
int n, m, q, l[200010], r[200010], a[200010];
long long dp[200010][20], ans[200010];
vector<int> queries;
void solve(int L, int R, vector<int> queries) {
    if (L == R) {
        for (int i = 0; i < queries.size(); i++) {
            ans[queries[i]] = 1 + (a[L] % m == 0);
        }
        return;
    }
    vector<int> left, right, now;
    int mid = (L + R) >> 1;
    for (int i = 0; i < queries.size(); i++) {
        if (r[queries[i]] <= mid) {
            left.push_back(queries[i]);
        } else if (l[queries[i]] > mid) {
            right.push_back(queries[i]);
        } else {
            now.push_back(queries[i]);
        }
    }
    solve(L, mid, left);
    solve(mid + 1, R, right);
    for (int i = 0; i < m; i++) {
        dp[mid][i] = dp[mid + 1][i] = 0;
    }
    dp[mid][0]++;
    dp[mid][a[mid] % m]++;
    dp[mid + 1][0]++;
    dp[mid + 1][a[mid + 1] % m]++;
    for (int i = mid - 1; i >= L; i--) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = dp[i + 1][j];
        }
        for (int j = 0; j < m; j++) {
            dp[i][(j + a[i]) % m] = (dp[i][(j + a[i]) % m] + dp[i + 1][j]) % mod;
        }
    }
    for (int i = mid + 2; i <= R; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        for (int j = 0; j < m; j++) {
            dp[i][(j + a[i]) % m] = (dp[i][(j + a[i]) % m] + dp[i - 1][j]) % mod;
        }
    }
    for (int i = 0; i < now.size(); i++) {
        for (int j = 0; j < m; j++) {
            ans[now[i]] = (ans[now[i]] + dp[l[now[i]]][j] * dp[r[now[i]]][(m - j) % m] % mod) % mod;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &l[i], &r[i]);
        queries.push_back(i);
    }
    solve(1, n, queries);
    for (int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}