불가사의한 버튼

당신은 마을 외곽에 있는 던전에서 코인을 벌기로 했다. 이 던전에는 1부터 $N$까지 번호가 붙은 $N$개의 방이 있다. 던전에는 “코인 버튼”, “탈출 버튼”, “워프 버튼”이라 불리는 신기한 버튼이 있다.

• 코인 버튼은 각 방에 정확히 1개씩 있다. 코인 버튼은 몇 번이고 누를 수 있으며, 누를 때마다 코인을 1개 얻는다.
• 탈출 버튼은 각 방에 정확히 1개씩 있다. 탈출 버튼을 누르면 즉시 던전에서 탈출하고 모험이 끝난다.
• 워프 버튼은 총 $M$개 있다. $i$번째 워프 버튼은 방 $a_i$에 있다. 이 버튼을 누르면 방 $b_i$로 워프하고 코인을 $c_i$개 얻는다. 단, $a_i < b_i$이고 $1 \le c_i \le 3$이다. 한 방에 워프 버튼이 여러 개 있을 수도 있고, 워프 버튼이 하나도 없는 방도 있다.

버튼을 누르는 것 외에는 방을 이동할 수 없으며, 버튼을 동시에 여러 개 누를 수도 없다. 모든 버튼은 서로 구별할 수 있다.

당신은 이 던전을 $Q$번 모험했다. 기억이 맞다면 $j$번째 모험은 방 1에서 시작해서, 마지막으로 방 $d_j$에 있는 탈출 버튼을 눌렀고, 코인을 정확히 $e_j$개 얻었다. 각 모험에 대해 이러한 버튼 누르는 방법이 몇 가지인지 구하라. 답이 클 수 있으므로 $10^9+7$로 나눈 나머지를 구하라.

두 가지 버튼 누르는 방법이 다르다는 것은, 누른 버튼의 총 횟수가 다르거나, 어떤 정수 $k$가 존재하여 $k$번째로 누른 버튼이 서로 다른 경우를 말한다.

기억이 잘못되었을 수도 있으며, 그런 방법이 존재하지 않을 수도 있다. 그 경우에는 0을 출력하라.

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

N M
a1 b1 c1
a2 b2 c2
...
aM bM cM
Q
d1 e1
d2 e2
...
dQ eQ

첫 줄에는 $N$과 $M$이 주어지며, $1 \le N, M \le 2000$을 만족한다. 이어지는 $M$개 줄에는 워프 버튼 정보가 주어지는데, $i$번째 줄에는 $a_i$, $b_i$, $c_i$가 주어진다. 여기서 $1 \le a_i < b_i \le N$이고 $1 \le c_i \le 3$이다. $M+2$번째 줄에는 $Q$가 주어지며, $1 \le Q \le 2000$을 만족한다. 이어지는 $Q$개 줄에는 $d_j$와 $e_j$가 주어지며, $1 \le d_j \le N$이고 $1 \le e_j \le 10^9$이다.

입력의 끝은 0 두 개로만 이루어진 줄이다. 데이터셋은 모두 50개를 넘지 않는다.

각 데이터셋에 대해 $Q$줄을 출력한다. $j$번째 줄에는 방 1에서 시작해 마지막으로 방 $d_j$에 있는 탈출 버튼을 눌러, 코인을 정확히 $e_j$개 얻는 버튼 누르는 방법의 총 개수를 $10^9+7$로 나눈 나머지로 출력한다.