問題文
Snuke 对计算多边形中的格子点很感兴趣,并了解了皮克定理。 我对网格点失去了兴趣。
所以,Snuke君准备了一架专机来鼓励他。
他准备的飞机是 xy 飞机 该区域满足 x,y≧0 ,但其网格点 以上每个(a,b)从 (0,0)开始,仅通过网格点并仅前进至↑和→。 到达(a,b)的方式数量,即 它被分配了值_{a+b}C_a。
Snuke非常喜欢这架飞机并问了他很多问题。
Snuke:“这个平面的边缘(两个轴)和 直线ax+by=c包围的区域中直角三角形内部和圆周上的网格点所写的值的总和是多少? ”
Sunake君:“我说这么大的数字你不会明白的。冷静点。”
Snuke:“哦不。然后用 mod 1000000007 回答我!”
Snuke没想到他玩得这么开心。请代表Snuke回答Snuke的问题!
入力
输入是按以下格式从标准输入给出的。
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) 这条线代表 Snuke 要求的直线。
配点
此题没有部分分。如果您正确回答所有测试用例,您将获得 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