不思議なボタン

あなたは，町外れにあるダンジョンでコインを稼ぐことにした．このダンジョンには N 個の部屋が存在し，1 から N までの番号がつけられている．また，ダンジョン内には「コインボタン」「脱出ボタン」「ワープボタン」と呼ばれる不思議なボタンが存在する．それぞれのボタンの詳細は次の通りである．

• コインボタンは各部屋にちょうど 1 個存在する．コインボタンは何回でも押すことができ，そのたびにコインが 1 枚手に入る．
• 脱出ボタンは各部屋にちょうど 1 個存在する．脱出ボタンを押すとあなたはただちにダンジョンから脱出し，この冒険を終了する．
• ワープボタンは合計で M 個存在する．このうち i 個目のワープボタンは部屋 a_i に存在し，押すことであなたは部屋 b_i にワープし，さらにコインが c_i 枚手に入る．ただし，a_i < b_i および 1 ≤ c_i ≤ 3 を満たす．なお，ワープボタンが 1 つの部屋に複数ある場合や，ワープボタンのまったく無い部屋が存在する場合もある．

なお，ボタンを押す以外の方法で部屋を移動することはできず，複数のボタンを同時に押すこともできない．また，いずれのボタンも互いに区別可能である．

あなたはこのダンジョンを Q 回冒険した．あなたの記憶が正しければ，j 回目の冒険は部屋 1 から始まり，最後に部屋 d_j にある脱出ボタンを押し，コインの合計獲得枚数はちょうど e_j 枚だったはずである．Q 回の冒険それぞれについて，そのようなボタンの押し方が何通りあるかを求めよ．答えは大きくなる可能性があるので，10⁹+7 すなわち 1000000007 で割った余りを求めよ．

ただし，2 通りの「ボタンの押し方」が異なるとは，ボタンを押した合計回数が異なるか，またはある整数 k が存在し，k 回目に押したボタンが異なることを指す．

なお，もしかしたらあなたの記憶は間違っており，そのようなボタンの押し方は存在しないかもしれない．その場合には 0 を出力せよ．

Input

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

N M a₁ b₁ c₁ a₂ b₂ c₂ ... a_M b_M c_M Q d₁ e₁ d₂ e₂ ... d_Q e_Q

データセットの 1 行目には，部屋の数を表す整数 N と，ワープボタンの数を表す整数 M が与えられ，1 ≤ N, M ≤ 2 000 を満たす．続く M 行にはワープボタンの情報が与えられる．M 行のうち i 行目には，i 番目のワープボタンの存在する部屋番号 a_i，ワープ先の部屋番号 b_i および手に入るコインの枚数 c_i が与えられ，1 ≤ a_i < b_i ≤ N および 1 ≤ c_i ≤ 3 を満たす．M+2 行目には冒険の回数を表す整数 Q が与えられ，1 ≤ Q ≤ 2 000 を満たす．続く Q 行にはあなたの記憶にある冒険の情報が与えられる．Q 行のうち j 行目には，j 番目の冒険であなたが脱出ボタンを押した部屋番号 d_j およびコインの獲得枚数 e_j が与えられ，1 ≤ d_j ≤ N および 1 ≤ e_j ≤ 10⁹ を満たす．

入力の終わりは，2 個のゼロだけからなる行で表される．全データセットの総数は 50 を超えない．

Output

各データセットについて出力は Q 行からなる．このうち j 行目には，部屋 1 から始まり，最後に部屋 d_j にある脱出ボタンを押し，コインの合計獲得枚数がちょうど e_j 枚であるようなボタンの押し方の総数を，10⁹+7 で割った余りを出力せよ．

Sample Input

4 9
1 2 1
1 2 2
1 3 1
1 3 2
1 3 3
2 3 1
2 3 2
1 4 1
3 4 2
8
1 5
2 5
3 5
4 5
1 1234567
2 1234567
3 1234567
4 1234567
4 8
1 2 1
1 2 1
1 2 3
3 4 3
1 4 2
2 4 1
2 4 3
2 4 3
8
1 3
2 6
3 8
4 12
1 31415926
2 53589793
3 23846
4 26433832
0 0

Output for the Sample Input

1
9
37
21
1
2469133
307629943
60012504
1
16
0
424
1
160769377
0
43581113