あなたは,町外れにあるダンジョンでコインを稼ぐことにした.このダンジョンには N 個の部屋が存在し,1 から N までの番号がつけられている.また,ダンジョン内には「コインボタン」「脱出ボタン」「ワープボタン」と呼ばれる不思議なボタンが存在する.それぞれのボタンの詳細は次の通りである.
なお,ボタンを押す以外の方法で部屋を移動することはできず,複数のボタンを同時に押すこともできない.また,いずれのボタンも互いに区別可能である.
あなたはこのダンジョンを Q 回冒険した.あなたの記憶が正しければ,j 回目の冒険は部屋 1 から始まり,最後に部屋 dj にある脱出ボタンを押し,コインの合計獲得枚数はちょうど ej 枚だったはずである.Q 回の冒険それぞれについて,そのようなボタンの押し方が何通りあるかを求めよ.答えは大きくなる可能性があるので,109+7 すなわち 1000000007 で割った余りを求めよ.
ただし,2 通りの「ボタンの押し方」が異なるとは,ボタンを押した合計回数が異なるか,またはある整数 k が存在し,k 回目に押したボタンが異なることを指す.
なお,もしかしたらあなたの記憶は間違っており,そのようなボタンの押し方は存在しないかもしれない.その場合には 0 を出力せよ.
入力は複数のデータセットからなる. 各データセットは次の形式で表される.
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 を超えない.
各データセットについて出力は Q 行からなる.このうち j 行目には,部屋 1 から始まり,最後に部屋 dj にある脱出ボタンを押し,コインの合計獲得枚数がちょうど ej 枚であるようなボタンの押し方の総数を,109+7 で割った余りを出力せよ.
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
1 9 37 21 1 2469133 307629943 60012504 1 16 0 424 1 160769377 0 43581113