#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 2005

struct Edge{
	Edge(int arg_to,int arg_value){
		to = arg_to;
		value = arg_value;
	}
	int to,value;
};

ll N,M;
int in_num[SIZE];
ll fact[3*SIZE],inverse_fact[3*SIZE];
ll dp[SIZE][3*SIZE];
ll head[SIZE],tail[SIZE];
vector<Edge> G[SIZE];


ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}


void func(){

	for(int i = 0; i < SIZE; i++){

		G[i].clear();
		in_num[i] = 0;
	}

	int from,to,value;

	for(int loop = 0; loop < M; loop++){

		scanf("%d %d %d",&from,&to,&value);
		from--;
		to--;

		G[from].push_back(Edge(to,value));

		in_num[to]++;
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k <= 3*N; k++){
			dp[i][k] = 0;
		}
	}

	dp[0][0] = 1;

	queue<int> Q;
	for(int i = 0; i < N; i++){
		if(in_num[i] == 0){
			Q.push(i);
		}
	}

	while(!Q.empty()){

		int node_id = Q.front();
		Q.pop();

		for(int i = 1; i <= 3*N; i++){

			dp[node_id][i] += dp[node_id][i-1];
			dp[node_id][i] %= MOD;

		}

		for(int i = 0; i <= 3*N-1; i++){
			if(dp[node_id][i] == 0)continue;

			for(int k = 0; k < G[node_id].size();k++){

				if(i+G[node_id][k].value > 3*N)continue;

				dp[G[node_id][k].to][i+G[node_id][k].value] += dp[node_id][i];
				dp[G[node_id][k].to][i+G[node_id][k].value] %= MOD;
			}
		}

		for(int k = 0; k < G[node_id].size(); k++){

			in_num[G[node_id][k].to]--;
			if(in_num[G[node_id][k].to] == 0){

				Q.push(G[node_id][k].to);
			}
		}
	}

	int num_query;
	scanf("%d",&num_query);

	int last_node;
	ll total;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d %lld",&last_node,&total);
		last_node--;

		if(total <= 3*N){

			printf("%lld\n",dp[last_node][total]);
			continue;
		}

		head[0] = 1;
		for(int i = 1; i <= N; i++){

			head[i] = head[i-1]*((total-2*N)-i+1);
			head[i] %= MOD;
		}

		tail[N] = 1;
		for(int i = N-1; i >= 0; i--){

			tail[i] = tail[i+1]*((total-2*N)-i-1);
			tail[i] %= MOD;
		}

		ll ans = 0;

		for(int i = 2*N; i <= 3*N; i++){

			ll tmp = dp[last_node][i];

			tmp *= head[i-2*N];
			tmp %= MOD;

			tmp *= tail[i-2*N];
			tmp %= MOD;

			ll denominator = (inverse_fact[i-2*N]*inverse_fact[3*N-i])%MOD;
			if((3*N-i)%2 == 1){

				denominator *= (-1+MOD);
				denominator %= MOD;
			}

			tmp *= denominator;
			tmp %= MOD;

			ans += tmp;
			ans %= MOD;
		}

		printf("%lld\n",ans);
	}
}

int main(){

	fact[0] = 1;
	for(ll i = 1; i <= 6000; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	inverse_fact[6000] = mod_inverse(fact[6000],MOD);
	for(ll i = 6000; i >= 1; i--){

		inverse_fact[i-1] = inverse_fact[i]*i;
		inverse_fact[i-1]%= MOD;
	}

	while(true){

		scanf("%lld %lld",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}


