Mysterious Button

You decide to earn coins in a dungeon on the outskirts of a town. The dungeon has $N$ rooms, numbered 1 to $N$. It contains three kinds of mysterious buttons: coin buttons, escape buttons, and warp buttons.

• Each room has exactly one coin button. You can press a coin button any number of times, and each press gives you 1 coin.
• Each room has exactly one escape button. Pressing it leaves the dungeon immediately and ends the adventure.
• There are $M$ warp buttons in total. The $i$-th warp button is in room $a_i$. Pressing it teleports you to room $b_i$ and gives you $c_i$ coins. Here $a_i < b_i$ and $1 \le c_i \le 3$. A room may have several warp buttons, and some rooms may have none.

You can move between rooms only by pressing buttons, and you cannot press several buttons at once. All buttons are distinguishable from each other.

You have explored this dungeon $Q$ times. If your memory is correct, the $j$-th adventure started in room 1 and ended by pressing the escape button in room $d_j$, collecting exactly $e_j$ coins in total. For each adventure, find the number of ways to press buttons that match this record. Two button sequences are different if they have different total numbers of presses, or if there is some integer $k$ such that the $k$-th pressed button differs. Since the answer can be large, print it modulo $10^9+7$.

Your memory may be wrong, in which case no such sequence exists. Then print 0.

The input consists of multiple datasets in the following format.

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

The first line of each dataset has $N$ and $M$, with $1 \le N, M \le 2000$. The next $M$ lines describe the warp buttons. Line $i$ contains $a_i$, $b_i$, and $c_i$, with $1 \le a_i < b_i \le N$ and $1 \le c_i \le 3$. Line $M+2$ contains $Q$, with $1 \le Q \le 2000$. The next $Q$ lines each contain $d_j$ and $e_j$, with $1 \le d_j \le N$ and $1 \le e_j \le 10^9$.

The input ends with a line containing two zeros. There are at most 50 datasets in total.

For each dataset, output $Q$ lines. Line $j$ contains the number of ways to press buttons that start in room 1, end by pressing the escape button in room $d_j$, and collect exactly $e_j$ coins in total, modulo $10^9+7$.