#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mod 998244353LL
#define ls(p) (p << 1)
#define rs(p) ((p << 1) | 1)
#define mid(p) ((tree[p].itl + tree[p].itr) >> 1)
using namespace std;

struct node{
	int itl, itr;
	vector<int> val;
} tree[800005];

int N, M, Q;
int l, r;
int A[200005];

void pushup(int p){
	for (int i = 0; i < M; i ++){
		if (tree[ls(p)].val[i] == 0) continue;
		for (int j = 0; j < M; j ++){
			tree[p].val[(i + j) % M] += (1LL * tree[ls(p)].val[i] * tree[rs(p)].val[j]) % mod;
			tree[p].val[(i + j) % M] %= mod;
		}
	}
}

void build(int p, int l, int r){
	tree[p] = {l, r};
	tree[p].val.resize(21);
	if (l == r){
		tree[p].val[A[l]] = 1;
		tree[p].val[0] += 1;
		return;
	}
	build(ls(p), l, mid(p));
	build(rs(p), mid(p) + 1, r);
	pushup(p);
}

vector<int> query(int p, int l, int r){
	if (l <= tree[p].itl && tree[p].itr <= r){
		return tree[p].val;
	}
	vector<int> tmp1, tmp2;
	int cnt = 0;
	if (l <= mid(p)){
		cnt += 1;
		tmp1 = query(ls(p), l, r);
	}
	if (r > mid(p)){
		cnt += 2;
		tmp2 = query(rs(p), l, r);
	}
	if (cnt == 1) return tmp1;
	if (cnt == 2) return tmp2;
	vector<int> res(21);
	for (int i = 0; i < M; i ++){
		if (tmp1[i] == 0) continue;
		for (int j = 0; j < M; j ++){
			res[(i + j) % M] += (1LL * tmp1[i] * tmp2[j]) % mod;
			res[(i + j) % M] %= mod;
		}
	}
	return res;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("../data.in", "r", stdin);
	freopen("../data.out", "w", stdout);
#endif

	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i ++){
		scanf("%d", &A[i]);
	}
	build(1, 1, N);
	scanf("%d", &Q);
	while (Q --){
		scanf("%d %d", &l, &r);
		vector<int> tmp = query(1, l, r);
		printf("%d\n", tmp[0] % mod);
	}

	return 0;
}