K. Counting Pairs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the quest of trying to be the best student ever, you pose your teacher an interesting question. You begin with two numbers, $$$x$$$ and $$$y$$$ both equal to $$$1$$$. You can do two operations, operation $$$1$$$ is to set $$$x := x + y$$$, and operation $$$2$$$ is to set $$$y := x + y$$$. The task is to count how many ways (modulo $$$10^9 + 7$$$) you can do operation $$$1$$$ or $$$2$$$ until $$$ax + by \gt c$$$. Two ways are different if either the number of operations is different or in one way you do operation $$$1$$$ instead of operation $$$2$$$. Because your teacher cannot solve the problem, you decide to help him out and solve it on your own.

Input

First line will contain a number $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$).

The next $$$t$$$ lines will each contain three numbers number $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \leq a,b,c \leq 2 \cdot 10^5$$$)

The sum of all $$$c$$$ does not exceed $$$10^6$$$

Output

For each of the $$$t$$$ testcases, print out the number of ways modulo $$$10^9 + 7$$$ for the given $$$a$$$, $$$b$$$, and $$$c$$$ in a new line.

Example
Input
7
1 1 4
1 1 5
1 2 5
2 3 5
3 3 5
1 1 100000
2 3 100000
Output
6
10
5
2
1
39650733
506608485
Note

For the first test case, we start at $$$(1, 1)$$$ (a xy pair will be represented as a coordinate).

Then we can go to in one operation: $$$(1, 2)$$$, $$$(2, 1)$$$

In two operations: $$$(3, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(3, 1)$$$

Note that $$$(3, 2)$$$ and $$$(2, 3)$$$ already finished.

In three operations: $$$(4, 3)$$$, $$$(3, 4)$$$, $$$(1, 4)$$$, $$$(4, 1)$$$

All $$$4$$$ of these finished too.

This means that the answer is $$$6$$$.