#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
const long long mod= 998244353;
int n,q,m;
int l[1900],r[1900],be[200005];
long long b[1900][1900][21];
long long pre[1900][1900][21],suf[1900][1900][21];
int a[200005];
void init(){
	int len = ceil(sqrt(n)/2.2),sq = n/len;
	for(int i =1;i<=sq;i++){
		l[i] = (i-1)*len+1,r[i] = i*len;
	}r[sq] = n;
	for(int i = 1;i<=sq;i++){
		pre[i][0][0] = 1;
		for(int j = l[i];j<=r[i];j++){
			be[j] = i;
			for(int k =0;k<m;k++){
				pre[i][j-l[i]+1][k] = (pre[i][j-l[i]][k]+pre[i][j-l[i]][(k-a[j]+m)%m])%mod;
			}
		}suf[i][0][0] = 1;
		for(int j = r[i];j>=l[i];j--){
			for(int k =0;k<m;k++){
				suf[i][r[i]-j+1][k] = (suf[i][r[i]-j][k]+suf[i][r[i]-j][(k-a[j]+m)%m])%mod;
			}
		}
	}for(int i = 1;i<=sq;i++){
		b[i][i-1][0] = 1;
		memcpy(b[i][i],suf[i][r[i]-l[i]+1],sizeof(b[i][i]));
		for(int j = i+1;j<=sq;j++){
			for(int k =0;k<m;k++){
				for(int ll =0;ll<m;ll++){
					b[i][j][(ll+k)%m] += (b[i][j-1][ll]*suf[j][r[j]-l[j]+1][k])%mod;
					b[i][j][(ll+k)%m]%=mod;
				}
			}
		}
	}return;
}long long res[20],ans[20];
inline int query(int x,int y){
	if(be[x] == be[y]){
		if(x == l[be[x]]){
			return pre[be[x]][y-x+1][0];
		}if(y == r[be[y]]){
			return suf[be[y]][y-x+1][0];
		}memset(res,0,sizeof(res));res[0] = 1;
		for(int i = x;i<=y;i++){
			memcpy(ans,res,sizeof(res));
			for(int j =0;j<m;j++){
				res[j] = (ans[j]+ans[(j-a[i]+m)%m])%mod;
			}
		}return res[0];
	}memset(res,0,sizeof(res));memset(ans,0,sizeof(ans));
	for(int i = 0;i<m;i++){
		for(int j = 0;j<m;j++){
			res[(i+j)%m] += suf[be[x]][r[be[x]]-x+1][i]*b[be[x]+1][be[y]-1][j]%mod;
			res[(i+j)%m] %= mod;
		}
	}for(int i =0;i<m;i++){
		for(int j =0 ;j<m;j++){
			ans[(i+j)%m] += pre[be[y]][y-l[be[y]]+1][i]*res[j]%mod;
			ans[(i+j)%m] %=mod;
		}
	}return ans[0];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i<=n;i++)cin >> a[i];
	init();cin >> q;//return 0;
	while(q--){
		int l,r;cin >> l >> r;
		cout << query(l,r) << '\n';
	}return 0;
}