Problem Description

Snuke, who was interested in counting lattice points inside polygons, learned about Pick's Theorem and lost interest in lattice points.

To encourage Snuke, Sanae prepared a special plane.

The plane he prepared was the region of the $xy$ plane where $x, y \geq 0$. On each lattice point $(a, b)$, the value assigned was the number of ways to reach $(a, b)$ from $(0, 0)$ by only moving up and right through lattice points, i.e., $_{a+b}C_a$.

Snuke loved this plane very much and started asking Sanae a lot of questions.

Snuke: "What is the sum of the values written on the lattice points inside and on the boundary of the right-angled triangle formed by the edges of this plane (the two axes) and the line $ax + by = c$?"

Sanae: "That's such a large number, it's hard to understand. Calm down."

Snuke: "No way! Okay, then tell me the answer modulo 1000000007!"

Sanae didn't expect Snuke to be so excited. Please answer Snuke's questions on Sanae's behalf!

Input Format

The input is given from the standard input in the following format:

$ Q $ $ a_1 $ $ b_1 $ $ c_1 $ . . . $ a_Q $ $ b_Q $ $ c_Q $

• The first line contains the number of queries $Q(1 \leq Q \leq 1000000)$.
• The following $ Q $ lines contain the query information. The $i+1\ (1 \leq i \leq Q)$ line contains the information for the $ i $th query, representing the line $ a_ix + b_iy = c_i $ $(1 \leq a_i, b_i, c_i \leq 10000)$ which Snuke is asking about.

Output Format

For each query $i(1 \leq i \leq Q)$, output the answer to the $ i $th query on a single line. Note that the answer should be given modulo 1000000007. Also, include a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
7 10 8
6 3 6
1 5 2

Sample Output #1

2
4
3

Sample Input #2

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

Sample Output #2

2
4
3
6
1

Notes/Hints

Scoring

There are no partial points for this problem. Correctly solving all test cases will award 100 points.

见题面 Input 部分

见题面 Output 部分