问题描述

苏努克君对计算多边形中的格点个数很感兴趣，但是他知道了皮克定理后对格点失去了兴趣。

因此，苏克君为了鼓励苏努克君，准备了一个特殊的平面。

他准备的平面是满足 $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)$ 表示苏努克君的问题所描述的直线。

输出

对于每个查询，输出一行答案，注意要对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