const int MAXN=2e5+5,MAXM=20,mod=1e9+7;
int ans[MAXN],a[MAXN],m;
struct query{
	int lef,rig,id;
};
int s[MAXN][MAXM],temp[MAXM<<1];
void solve(int lef,int rig,vector<query> b){
	int mid=lef+rig>>1;
	if(lef==rig){
		_for(i,0,b.size())
		ans[b[i].id]=1+(a[mid]==0);
		return;
	}
	mem(s[mid],0);
	s[mid][0]++;
	s[mid][a[mid]]++;
	for(int i=mid-1;i>=lef;i--){
		_for(j,0,m)
		s[i][(a[i]+j)%m]=(s[i+1][(a[i]+j)%m]+s[i+1][j])%mod;
	}
	mem(s[mid+1],0);
	s[mid+1][0]++;
	s[mid+1][a[mid+1]]++;
	for(int i=mid+2;i<=rig;i++){
		_for(j,0,m)
		s[i][(a[i]+j)%m]=(s[i-1][(a[i]+j)%m]+s[i-1][j])%mod;
	}
	vector<query>b1,b2;
	_for(i,0,b.size()){
		if(b[i].rig<=mid)
		b1.push_back(b[i]);
		else if(b[i].lef>mid)
		b2.push_back(b[i]);
		else{
			mem(temp,0);
			_for(j,0,m)_for(k,0,m)
			temp[j+k]=(temp[j+k]+1LL*s[b[i].lef][j]*s[b[i].rig][k])%mod;
			ans[b[i].id]=(temp[0]+temp[m])%mod;
		}
	}
	solve(lef,mid,b1);
	solve(mid+1,rig,b2);
}
int main()
{
	int n=read_int();
	m=read_int();
	_rep(i,1,n)a[i]=read_LL()%m;
	int q=read_int();
	vector<query> b;
	_for(i,0,q){
		int l=read_int(),r=read_int();
		b.push_back(query{l,r,i});
	}
	solve(1,n,b);
	_for(i,0,q)
	enter(ans[i]);
	return 0;
}

const int MAXN=2e5+5,MAXM=2e5+5,MAXV=22;
namespace Tree{
	struct Edge{
		int to,id,next;
	}edge[MAXN+MAXM];
	int head1[MAXN],head2[MAXN],edge_cnt;
	int deg[MAXN],f[MAXN],dep[MAXN],anc[MAXN][MAXV],lg2[MAXN];
	int deg0[MAXN];
	void Insert1(int u,int v,int id){
		edge[++edge_cnt]=Edge{v,id,head1[u]};
		head1[u]=edge_cnt;
		deg[v]++;
		deg0[v]++;
	}
	void Insert2(int u,int v){
		edge[++edge_cnt]=Edge{v,0,head2[u]};
		head2[u]=edge_cnt;
	}
	int LCA(int u,int v){
		if(dep[u]<dep[v])
		swap(u,v);
		while(dep[u]>dep[v])u=anc[u][lg2[dep[u]-dep[v]]];
		if(u==v)
		return u;
		for(int i=MAXV-1;i>=0;i--){
			if(anc[u][i]!=anc[v][i])
			u=anc[u][i],v=anc[v][i];
		}
		return anc[u][0];
	}
	int build(int n){
		lg2[1]=0;
		_for(i,2,MAXN)lg2[i]=lg2[i>>1]+1;
		int rt=n+1;
		queue<int> q;
		_rep(i,1,n){
			if(deg[i]==0){
				f[i]=rt;
				q.push(i);
			}
		}
		while(!q.empty()){
			int u=q.front();q.pop();
			dep[u]=dep[f[u]]+1;
			Insert2(f[u],u);
			anc[u][0]=f[u];
			for(int i=1;i<MAXV;i++)
			anc[u][i]=anc[anc[u][i-1]][i-1];
			for(int i=head1[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(f[v]==0)
				f[v]=u;
				else
				f[v]=LCA(u,f[v]);
				deg[v]--;
				if(deg[v]==0)
				q.push(v);
			}
		}
		return rt;
	}
	int sz[MAXN],ans[MAXM];
	void dfs(int u){
		sz[u]=1;
		for(int i=head2[u];i;i=edge[i].next){
			int v=edge[i].to;
			dfs(v);
			sz[u]+=sz[v];
		}
	}
	void solve(int n,int m){
		int rt=build(n);
		dfs(rt);
		_rep(u,1,n){
			for(int i=head1[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(deg0[v]==1)
				ans[edge[i].id]=sz[v];
			}
		}
		_for(i,0,m)
		enter(ans[i]);
	}
}
struct Edge{
	int to,w,id,next;
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v,int w,int id){
	edge[++edge_cnt]=Edge{v,w,id,head[u]};
	head[u]=edge_cnt;
}
LL dis[MAXN];
bool vis[MAXN];
int main(){
	int n=read_int(),m=read_int();
	_for(i,0,m){
		int u=read_int(),v=read_int(),w=read_int();
		Insert(u,v,w,i);
		Insert(v,u,w,i);
	}
	priority_queue<pair<LL,int> >q;
	mem(dis,127);
	dis[1]=0;
	q.push(make_pair(-dis[1],1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
	_rep(u,1,n){
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to;
			if(dis[v]==dis[u]+edge[i].w)
			Tree::Insert1(u,v,edge[i].id);
		}
	}
	Tree::solve(n,m);
	return 0;
}