時間制限 : sec, メモリ制限 : KB
Japanese

不思議なボタン

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

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

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

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

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

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

Input

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

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

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

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

Output

各データセットについて出力は Q 行からなる.このうち j 行目には,部屋 1 から始まり,最後に部屋 dj にある脱出ボタンを押し,コインの合計獲得枚数がちょうど ej 枚であるようなボタンの押し方の総数を,109+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