#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, P = 998244353;

int n,m,a[N];

long long f[N][25];

int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i], a[i] %= m;
    int q; cin >> q;
    while (q--){
        int l,r;
        cin >> l >> r;
        memset(f[l - 1],0,sizeof(f[l - 1]));
        f[l - 1][0] = 1;
        for (int i = l;i <= r;i++){
            for (int j = 0;j < m;j++)
                f[i][j] = f[i - 1][j];
            for (int j = 0;j < m;j++){
                (f[i][(j + a[i]) % m] += f[i - 1][j]) %= P;
            }
        }
        cout << f[r][0] << '\n';
    }
}