Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

Chef has a clock, but it got broken today — the minute hand on Chef's clock doesn't rotate by the angle 2π/3600 each second, but by a different fixed angle x. The coordinates of the center of the clock are (0, 0). The length of the minute hand is l.

One endpoint of the minute hand is always located at the clock center; the other endpoint is initially located at the point (0, l). One second later, Chef observes that this endpoint is at distance d above the x-axis, i.e. the y-coordinate of this endpoint is equal to d.

Chef is curious about where the minute hand will be (specifically, its y-coordinate) after t seconds. Because t can be very large, Chef can't wait for that moment. Please help him!

------ Input ------

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains three space-separated integers l, d and t.

------ Output ------

We can prove that for the given constraints, the y-coordinate of the end of the minute hand can always be written as a rational number p / q, where gcd(p, q) = gcd(q, 10^{9} + 7) = 1. Let's denote the modular inverse of q (it's guaranteed that the modular inverse exists and is unique) by r.

For each test case, print a single line containing one number (p · r) modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ d < l ≤ 10^{9}$
$1 ≤ t ≤ 10^{18}$

------ Subtasks ------

Subtask #1 (5 points): t ≤ 3

Subtask #2 (15 points): t is a power of 2, i.e. t = 2^{p} for some p ≥ 0

Subtask #3 (40 points): sum of t over all test cases ≤ 10^{6}

Subtask #4 (40 points): original constraints

----- Sample Input 1 ------
3
4 2 1
4 2 2
4 2 3
----- Sample Output 1 ------
2
1000000005
1000000003
----- explanation 1 ------
Example case 1:

Example case 2:

The y-coordinate is -2, so the answer is 1000000005.

Example case 3:

The y-coordinate is -4, so the answer is 1000000003.

见题面

见题面