Broken Clock

All submissions for this problem are available.
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 xaxis, i.e. the ycoordinate of this endpoint is equal to d.
Chef is curious about where the minute hand will be (specifically, its ycoordinate) 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 spaceseparated integers l, d and t.
Output
We can prove that for the given constraints, the ycoordinate 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
Example
Input: 3 4 2 1 4 2 2 4 2 3 Output: 2 1000000005 1000000003
Explanation
Example case 1:
Example case 2:
The ycoordinate is 2, so the answer is 1000000005.
Example case 3:
The ycoordinate is 4, so the answer is 1000000003.
Author:  chemthan 
Tester:  r_64 
Editorial  https://discuss.codechef.com/problems/BROCLK 
Tags  chemthan, feb18, math, matrixexpo, modulararith, trigonometry 
Date Added:  23082017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions