22387번 - 不思議なボタン 다국어

문제

あなたは,町外れにあるダンジョンでコインを稼ぐことにした.このダンジョンには 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 を出力せよ.

입력

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

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 番目のワープボタンの存在する部屋番号 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 を超えない.

출력

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

제한

힌트