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 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!
- 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.
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, 109 + 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 109 + 7.
- 1 ≤ T ≤ 105
- 1 ≤ d < l ≤ 109
- 1 ≤ t ≤ 1018
Subtask #1 (5 points): t ≤ 3
Subtask #2 (15 points): t is a power of 2, i.e. t = 2p for some p ≥ 0
Subtask #3 (40 points): sum of t over all test cases ≤ 106
Subtask #4 (40 points): original constraints
Input: 3 4 2 1 4 2 2 4 2 3 Output: 2 1000000005 1000000003
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.
|Tags||chemthan, feb18, math, matrix-expo, modular-arith, trigonometry|
|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, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.