C - 格子点 解説 /

実行時間制限: 4 sec / メモリ制限: 256 MB

問題文

多角形の中の格子点を数えることに興味を持っていたすぬけ君はピックの定理を知り、 格子点に対する興味を失ってしまった。

そこで、すなけ君はすぬけ君を励ますために特別な平面を用意した。

彼が用意した平面は xy 平面の x,y≧0 を満たす領域であったが、その格子点(a,b)の各々の上には (0,0)から格子点だけを通って↑と→にだけ進んで(a,b)に到達する方法の数、すなわち_{a+b}C_aという値が割り当てられていた。

すぬけ君はこの平面をとても気に入り、すなけ君にたくさんの質問をしてきた。

すぬけ君「この平面の端（二つの軸）とax+by=cという直線に囲まれた領域の直角三角形の内部と周上に存在する格子点に書かれている値の和っていくつ？」

すなけ君「こらこらそんな大きな数言ってもわからないでしょ。落ち着きなさい。」

すぬけ君「やだー。じゃあ mod 1000000007 でいいから答えて！」

すなけ君はこんなにすぬけ君がはしゃぐとは思っていませんでした。すなけ君の代わりにすぬけ君の質問に答えてください！

入力

入力は以下の形式で標準入力から与えられる。

 Q 
 a_1  b_1 c_1 
.
.
.
 a_Q  b_Q c_Q
  • 一行目にはクエリの数 Q(1≦Q≦1000000) が与えられる。
  • 続く Q 行には、クエリの情報が与えられる。 i+1 (1≦i≦Q) 行目にはi 個目のクエリの情報が与えられ、a_ix+b_iy=c_i (1≦a_i,b_i,c_i≦10000) がすぬけ君の質問する直線を表している。

配点

この問題には部分点がありません。すべてのテストケースに正解すれば100点です。

出力

　i(1≦i≦Q) 行目には i 個目のクエリに対する答えを一行に出力せよ。mod 1000000007 で答えることに注意すること。また、出力の末尾に改行を入れること。

入力例1

3
7 10 8
6 3 6
1 5 2

出力例1

2
4
3

入力例2

5
10 4 7
8 1 3
4 4 7
1 10 5
8 8 5

出力例2

2
4
3
6
1