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.

Difficulty: HARD
Tags: Geometry

Number theory

Matrices

Mathematics

Starter code:

Solutions:
md = 10 ** 9 + 7

def mmul(a, b, adj):
	c0 = (a[0] * b[0] + a[1] * b[1] * adj) % md
	c1 = (a[0] * b[1] + a[1] * b[0]) % md
	return (c0, c1)

def mpow(b, adj, t):
	rv = (1, 0)
	while True:
		if t % 2 != 0:
			rv = mmul(rv, b, adj)
		t //= 2
		if t == 0:
			return rv
		b = mmul(b, b, adj)
for _ in range(int(input())):
	(l, d, t) = (int(x) for x in input().split())
	(y, __) = mpow((d, 1), d ** 2 - l ** 2, t)
	print(y * pow(l, 1 - t, md) % md)


def prod(a, b):
	ans00 = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % m
	ans01 = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % m
	ans10 = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % m
	ans11 = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % m
	return ([ans00, ans01], [ans10, ans11])

def matexpo(a, b):
	c = [[1, 0], [0, 1]]
	while b > 0:
		if b % 2 == 1:
			c = prod(c, a)
		(b, a) = (b // 2, prod(a, a))
	return c
m = 1000000007
for T in range(int(input())):
	(l, d, t) = [int(x) for x in input().split()]
	mt = matexpo([[2 * (d * pow(l, m - 2, m)), -1], [1, 0]], t - 1)
	print(l * ((mt[0][0] * (d * pow(l, m - 2, m)) + mt[0][1]) % m) % m)


def prod(a, b):
	ans00 = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % m
	ans01 = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % m
	ans10 = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % m
	ans11 = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % m
	return ([ans00, ans01], [ans10, ans11])

def matexpo(a, b):
	n = len(a)
	c = [[1, 0], [0, 1]]
	while b > 0:
		if b % 2 == 1:
			c = prod(c, a)
		b //= 2
		a = prod(a, a)
	return c
import math
m = 1000000007
for T in range(int(input())):
	(l, d, t) = [int(x) for x in input().split()]
	cosx = d * pow(l, m - 2, m)
	mt = [[2 * cosx, -1], [1, 0]]
	mt = matexpo(mt, t - 1)
	costx = (mt[0][0] * cosx + mt[0][1]) % m
	print(l * costx % m)


mod = 1000000007

def matmult(a, b):
	c00 = a[0][0] * b[0][0] + a[0][1] * b[1][0]
	c01 = a[0][0] * b[0][1] + a[0][1] * b[1][1]
	c10 = a[1][0] * b[0][0] + a[1][1] * b[1][0]
	c11 = a[1][0] * b[0][1] + a[1][1] * b[1][1]
	c00 %= mod
	c01 %= mod
	c10 %= mod
	c11 %= mod
	return [[c00, c01], [c10, c11]]

def matpow(a, b):
	n = len(a)
	c = [[1, 0], [0, 1]]
	while b > 0:
		if b % 2:
			c = matmult(c, a)
		b = b // 2
		a = matmult(a, a)
	return c
for _ in range(int(input())):
	(l, d, t) = map(int, input().split())
	cosx = d * pow(l, mod - 2, mod) % mod
	mat = [[2 * cosx, -1], [1, 0]]
	mat = matpow(mat, t - 1)
	costx = (mat[0][0] * cosx + mat[0][1]) % mod
	print(l * costx % mod)


def pow(a, b, c):
	n = 1
	m = a
	v = b
	if a == 1:
		return 1
	while v > 0:
		if v % 2 == 1:
			n *= m % c
			n %= c
		m *= m
		m %= c
		v //= 2
	return n % c

def mul(a, b, c, mod):
	return [(a[0] * b[0] % mod + a[1] * b[1] % mod * c % mod % mod) % mod, (a[0] * b[1] + a[1] * b[0]) % mod]

def pow_cos(a, b, cos2, mod):
	n = [1, 0]
	m = a
	v = b
	if a == [1, 0]:
		return [1, 0]
	while v > 0:
		if v % 2 == 1:
			n = mul(n, m, cos2, mod)
		m = mul(m, m, cos2, mod)
		m[0] %= mod
		m[1] %= mod
		v //= 2
	return n
mod = 1000000007
T = int(input())
for _ in range(T):
	(l, d, t) = map(int, input().split())
	cos = d * pow(l, mod - 2, mod) % mod
	cos2 = (cos ** 2 - 1) % mod
	ans = pow_cos([cos, 1], t, cos2, mod)[0]
	ans *= l
	ans %= mod
	print(ans)


mod = 10 ** 9 + 7

def multiplymod(P, Q):
	R = [[0, 0], [0, 0]]
	R[0][0] = (P[0][0] * Q[0][0] + P[0][1] * Q[1][0]) % mod
	R[0][1] = (P[0][0] * Q[0][1] + P[0][1] * Q[1][1]) % mod
	R[1][0] = (P[1][0] * Q[0][0] + P[1][1] * Q[1][0]) % mod
	R[1][1] = (P[1][0] * Q[0][1] + P[1][1] * Q[1][1]) % mod
	return R

def power(A, n, base):
	res = [[1, 0], [0, 1]]
	while n > 0:
		if n % 2 == 1:
			res = multiplymod(res, A)
		n = n // 2
		A = multiplymod(A, A)
	return res

def cosnx(a, n):
	M = [[2 * a, mod - 1], [1, 0]]
	M = power(M, n - 1, a)
	return (M[0][0] * a + M[0][1]) % mod
for _ in range(int(input())):
	(l, d, t) = map(int, input().split())
	if t == 1:
		print(d)
	else:
		cosx = d * pow(l, mod - 2, mod) % mod
		ans = cosnx(cosx, t) * l % mod
		print(ans)


mod = 10 ** 9 + 7

def fastpow(a, n):
	res = 1
	a %= mod
	while n > 0:
		if n % 2 == 1:
			res = res * a % mod
		n = n // 2
		a = a * a % mod
	return res

def multiplymod(P, Q):
	R = [[0, 0], [0, 0]]
	R[0][0] = (P[0][0] * Q[0][0] + P[0][1] * Q[1][0]) % mod
	R[0][1] = (P[0][0] * Q[0][1] + P[0][1] * Q[1][1]) % mod
	R[1][0] = (P[1][0] * Q[0][0] + P[1][1] * Q[1][0]) % mod
	R[1][1] = (P[1][0] * Q[0][1] + P[1][1] * Q[1][1]) % mod
	return R

def power(A, n, base):
	res = [[1, 0], [0, 1]]
	while n > 0:
		if n % 2 == 1:
			res = multiplymod(res, A)
		n = n // 2
		A = multiplymod(A, A)
	return res

def getcosnx(a, n):
	M = [[2 * a, mod - 1], [1, 0]]
	M = power(M, n - 1, a)
	return (M[0][0] * a + M[0][1]) % mod
T = int(input())
for tc in range(T):
	(l, d, t) = map(int, input().split())
	if t == 1:
		print(d)
		continue
	cosx = d * fastpow(l, mod - 2) % mod
	ans = getcosnx(cosx, t) * l % mod
	print(ans)


mod = 1000000007

def fast_exp(x, e):
	ret = 1
	while e:
		if e & 1:
			ret = ret * x % mod
		x = x * x % mod
		e >>= 1
	return ret

def inv(x):
	return fast_exp(x, mod - 2)

class matrix:

	def __init__(self):
		self.a = 1
		self.b = 0
		self.c = 0
		self.d = 1

	def multiply(self, p, q, r, s):
		e = (self.a * p + self.b * r) % mod
		f = (self.a * q + self.b * s) % mod
		g = (self.c * p + self.d * r) % mod
		h = (self.c * q + self.d * s) % mod
		(self.a, self.b, self.c, self.d) = (e, f, g, h)

def fast_matrix_exp(m, x):
	ret = matrix()
	while x:
		if x & 1:
			ret.multiply(m.a, m.b, m.c, m.d)
		m.multiply(m.a, m.b, m.c, m.d)
		x >>= 1
	return ret
T = int(input())
while T != 0:
	(l, d, t) = input().split()
	l = int(l)
	d = int(d)
	t = int(t)
	mt = matrix()
	mt.a = 2 * d * inv(l) % mod
	mt.b = mod - 1
	mt.c = 1
	mt.d = 0
	mt = fast_matrix_exp(mt, t - 1)
	print((mt.a * d + mt.b * l + mod) % mod)
	T = T - 1


import sys
base = 10 ** 9 + 7
from math import gcd
sys.setrecursionlimit(3000)

def cos(l, d, t, space):
	if t == 0:
		space[t] = 1
		return 1
	elif t == 1:
		space[t] = d * modinv(l)
		return d * modinv(l)
	elif t in space:
		return space[t]
	elif t % 2 == 0:
		if t // 2 in space:
			space[t] = (2 * pow(space[t // 2], 2, base) - 1) % base
			return space[t]
		else:
			space[t] = (2 * pow(cos(l, d, t // 2, space), 2, base) - 1) % base
			return space[t]
	else:
		if t // 2 in space:
			v1 = space[t // 2]
		else:
			v1 = cos(l, d, t // 2, space)
			space[t // 2] = v1
		if t // 2 + 1 in space:
			v2 = space[t // 2 + 1]
		else:
			v2 = cos(l, d, t // 2 + 1, space)
			space[t // 2 + 1] = v2
		space[t] = (2 * v1 * v2 - space[1]) % base
		return space[t]

def modinv(a):
	return pow(a, base - 2, base)
for i in range(int(input())):
	(l, d, t) = map(int, input().split())
	space = {}
	comm = gcd(l, d)
	l1 = l // comm
	d1 = d // comm
	print(l * cos(l1, d1, t, space) % base)


MOD = 1000000007

def poww(x, y, mod=MOD):
	if y <= 0:
		return 1
	if y == 1:
		return x % MOD
	if y % 2 == 0:
		pp = poww(x, y // 2) % mod
		return pp * pp % mod
	else:
		pp = poww(x, y // 2) % mod
		return pp * pp % mod * x % mod

def inv_mod(x, mod):
	return poww(x, mod - 2, mod)

def isPowerTwo(num):
	return num != 0 and num & num - 1 == 0

def matmull(a, b):
	xx = [[0, 0], [0, 0]]
	xx[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD
	xx[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD
	xx[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD
	xx[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD
	return xx

def matpow(mm, n):
	if n == 1:
		return mm
	if n % 2 == 0:
		pp = matpow(mm, n // 2)
		return matmull(pp, pp)
	else:
		pp = matpow(mm, n // 2)
		return matmull(matmull(pp, pp), mm)

def mulll(a, b):
	xx = [0, 0]
	xx[0] = (a[0][0] * b[0] + a[0][1] * b[1]) % MOD
	xx[1] = (a[1][0] * b[0] + a[1][1] * b[1]) % MOD
	return xx
t = int(input())
while t > 0:
	t -= 1
	(l, d, n) = map(int, input().split())
	x = d * inv_mod(l, MOD) % MOD
	first = x
	second = ((2 * x % MOD * x % MOD - 1) % MOD + MOD) % MOD
	if n == 1:
		print(d)
		continue
	if n == 2:
		ans = (second * l % MOD + MOD) % MOD
		print(ans)
		continue
	mm = [[2 * x, -1], [1, 0]]
	bb = [x, 1]
	n -= 1
	xx = [[0, 0], [0, 0]]
	xx = matpow(mm, n)
	xx = mulll(xx, bb)
	print(xx[0] * l % MOD)


import random
import math
TEST = False
if not TEST:
	T = int(input())
else:
	T = 100000
M = 10 ** 9 + 7

def simplify(p, q):
	r = math.gcd(p, q)
	p = p // r
	q = q // r
	return (p, q)

def chebyshev(n, a):
	if n == 0:
		return 1
	if n == 1:
		return a
	if n in mem:
		return mem[n]
	if n & 1 == 0:
		b = chebyshev(n // 2, a)
		c = 2 * b * b - 1
		c %= M
		mem[n] = c
		return c
	else:
		b2 = chebyshev(n // 2, a)
		b1 = chebyshev(n // 2 + 1, a)
		c = 2 * b1 * b2 - a
		c %= M
		mem[n] = c
		return c
for _ in range(T):
	if not TEST:
		(l, d, t) = [int(c) for c in input().strip().split()]
	else:
		l = random.randrange(10 ** 9) + 1
		d = random.randrange(l) + 1
		t = 1 + random.randrange(10 ** 18)
	mem = dict()
	r = pow(l, M - 2, M)
	a = d * r
	a %= M
	b = chebyshev(t, a)
	rep = b * l
	rep = rep % M
	print(rep)


def f(t, R, Y, C):
	if t == 1:
		return Y
	(f0, f1, i) = (R, Y, 2)
	mat = modpow([[0, 1], [-1, 2 * C]], t - 1)
	return mat[1][0] * R + mat[1][1] * Y

def egcd(a, b):
	(prevx, x) = (1, 0)
	(prevy, y) = (0, 1)
	while b:
		q = a // b
		(x, prevx) = (prevx - q * x, x)
		(y, prevy) = (prevy - q * y, y)
		(a, b) = (b, a % b)
	return (a, prevx, prevy)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def mul(m1, m2):
	return [[(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD], [(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD]]

def modpow(mat, p):
	if p == 1:
		return mat
	elif p % 2 == 0:
		ans = modpow(mat, p // 2)
		return mul(ans, ans)
	else:
		ans = modpow(mat, p - 1)
		return mul(mat, ans)
MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(l, d, t) = map(int, input().split())
	c = d * modinv(l, MOD) % MOD
	ans = f(t, l, d, c)
	print(ans % MOD)


(d, u, m) = (0, 0, 10 ** 9 + 7)

def solve(l, r):
	if r == 0:
		return (1, 0, 0, 1)
	if r & 1:
		(x, y, z, w) = solve(l, r - 1)
		return ((2 * u * x + d * y) % m, -d * x % m, (2 * u * z + d * w) % m, -d * z % m)
	(x, y, z, w) = solve(l, r // 2)
	return ((x * x + y * z) % m, (x * y + y * w) % m, (x * z + w * z) % m, (y * z + w * w) % m)
for _ in range(int(input())):
	(d, u, t) = list(map(int, input().split()))
	l = solve((2 * u, -d, d, 0), t - 1)
	ans = (l[0] * u + l[1] * d) * pow(pow(d, t - 1, m), m - 2, m) % m
	print(ans)


import math
from fractions import gcd

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, mod) % mod
	p = p * p % mod
	if y % 2 == 0:
		return p
	return x * p % mod
val = [0] * 64
val[0] = 1
mod = 1000000007
for i in range(1, 63):
	val[i] = val[i - 1] * 2
for _ in range(eval(input())):
	l = 0
	y = 0
	y1 = 0
	v0 = 0
	arr = [0] * 64
	ps = [0] * 64
	si = [0] * 64
	co = [0] * 64
	ro = 0
	t1 = 0
	i = 0
	v = 1
	fl = 0
	pr = 0
	f = 0
	(l, y, t1) = map(int, input().split())
	f = gcd(y, l)
	p = power(l // f, mod - 2, mod) % mod
	v0 = (p * (y // f) % mod + mod) % mod
	arr[0] = v0
	ps[0] = 1
	for i in range(1, 64):
		arr[i] = ((2 * arr[i - 1] * arr[i - 1] % mod - 1) % mod + mod) % mod
		ps[i] = ps[i - 1] * (2 * arr[i - 1] % mod) % mod
	v = 1
	for i in range(0, 64):
		if val[i] > t1:
			break
		elif val[i] & t1:
			if fl != 0:
				si[i] = co[pr] * ps[i] % mod + arr[i] * si[pr] % mod % mod
				co[i] = ((co[pr] * arr[i] % mod - si[pr] * ps[i] % mod * (1 - v0 * v0 % mod) % mod % mod) % mod + mod) % mod
				v = co[i]
				pr = i
			else:
				v = arr[i]
				si[i] = ps[i]
				co[i] = v
				fl = 1
				pr = i
	print(v * l % mod)


import math
import copy
import sys

def modInverse(a, m):
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def fcos2px(cosx, t):
	m = 10 ** 9 + 7
	(n, d) = cosx
	p = 1
	while p < t:
		n = (2 * power(n, 2, m) % m - power(d, 2, m) % m) % m
		d = power(d, 2, m)
		p = p * 2
	return n

def isPowerOfTwo(n):
	if n == 0:
		return False
	while n != 1:
		if n % 2 != 0:
			return False
		n = n // 2
	return True

def multiply(A, B):
	m = 10 ** 9 + 7
	x00 = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % m
	x01 = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % m
	x10 = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % m
	x11 = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % m
	return [[x00, x01], [x10, x11]]

def matrix_power(A, x):
	result = [[1, 0], [0, 1]]
	while x > 0:
		if x & 1 != 0:
			result = multiply(result, A)
		A = multiply(A, A)
		x = x >> 1
	return result
r = int(input())
for _ in range(r):
	(l, d, t) = map(int, sys.stdin.readline().split(' '))
	m = 10 ** 9 + 7
	c = [d, l]
	log = math.log
	num = 0
	if t == 1:
		num = d
	elif isPowerOfTwo(t):
		num = fcos2px(c, t)
	else:
		A = [[2 * d % m, -1 * power(l, 2, m)], [1, 0]]
		A = matrix_power(A, t - 1)
		num = (d * A[0][0] % m % m + A[0][1]) % m
	ans = l % m * (num % m) % m * power(l, t * (m - 2), m) % m
	print(ans)


def modInverse(a, m):
	(g, x, y) = gcdExtended(a, m)
	if g != 1:
		return -1
	res = (x % m + m) % m
	return res

def gcdExtended(a, b):
	if a == 0:
		return (b, 0, 1)
	(gcd, x1, y1) = gcdExtended(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (gcd, x, y)

def exponential_modulo(n, k, m):
	if n == 0:
		return 0
	elif k == 0:
		return 1
	(t, k1) = (k % 2, k // 2)
	n1 = n * n % m
	if t == 1:
		return exponential_modulo(n1, k1, m) * (n % m) % m
	else:
		return exponential_modulo(n1, k1, m) % m

def prerequisites(l, d, t, m):
	cosine = [d]
	sine = [1]
	powerl = [l]
	pow2 = 2
	while pow2 <= t:
		powerl.append(powerl[-1] * powerl[-1] % m)
		c = (2 * cosine[-1] * cosine[-1] % m - powerl[-1] + m) % m
		s = (2 * sine[-1] * cosine[-1] + m * m) % m
		cosine.append(c)
		sine.append(s)
		pow2 *= 2
	return (sine, cosine, powerl)
m = 1000000007
for test in range(int(input().strip())):
	(l, d, t) = map(int, input().strip().split())
	origl = l
	(gcd, x, y) = gcdExtended(d, l)
	(l, d) = (l // gcd, d // gcd)
	perpend = l * l - d * d
	(sine, cosine, powerl) = prerequisites(l, d, t, m)
	binaryt = bin(t)[::-1]
	cs = None
	si = None
	for i in range(0, len(binaryt) - 2):
		if binaryt[i] == '1':
			if cs == None:
				cs = cosine[i]
				si = sine[i]
			else:
				cs1 = cs
				cs = (cosine[i] * cs % m - sine[i] * si % m * perpend % m + m * m) % m
				si = (sine[i] * cs1 % m + cosine[i] * si % m + m) % m
	inver = modInverse(l, m)
	inver = exponential_modulo(inver, t - 1, m)
	ans = cs * inver * gcd % m
	print(ans)


from collections import Counter
from itertools import groupby
mod = 10 ** 9 + 7

class Root:

	def __init__(self, a, b, c):
		self.real = a
		self.imag = b
		self.imag_mod = c

	def __mul__(self, c2):
		real = (self.real * c2.real + self.imag * c2.imag * self.imag_mod) % mod
		imag = (self.real * c2.imag + self.imag * c2.real) % mod
		return Root(real, imag, self.imag_mod)

	def __pow__(self, n):
		res = Root(1, 0, self.imag_mod)
		val = self
		while n:
			if n % 2:
				res *= val
			val *= val
			n //= 2
		return res
for _ in range(int(input())):
	(I, d, t) = [int(x) for x in input().split()]
	i = pow(I, mod - 2, mod)
	z = Root(d * i % mod, 1, (d ** 2 - I ** 2) * i ** 2 % mod)
	z = z.__pow__(t)
	f = z.real * I % mod
	print(f)


import math
from fractions import Fraction

def modInverse(a, tmp, m):
	return pow(a, tmp, m)

def matrixPower(M, n):
	if n == 1:
		return M
	else:
		P = matrixPower(M, n // 2)
		a11 = (P[0][0] ** 2 + P[0][1] * P[1][0]) % 1000000007
		a12 = (P[0][0] + P[1][1]) * P[0][1] % 1000000007
		a21 = (P[0][0] + P[1][1]) * P[1][0] % 1000000007
		a22 = (P[1][1] ** 2 + P[0][1] * P[1][0]) % 1000000007
		P = [[a11, a12], [a21, a22]]
		if n % 2 == 0:
			return P
		else:
			a11 = (P[0][0] * M[0][0] + P[0][1] * M[1][0]) % 1000000007
			a12 = (P[0][0] * M[0][1] + P[0][1] * M[1][1]) % 1000000007
			a21 = (P[1][0] * M[0][0] + P[1][1] * M[1][0]) % 1000000007
			a22 = (P[1][0] * M[0][1] + P[1][1] * M[1][1]) % 1000000007
			return [[a11, a12], [a21, a22]]
t = int(input())
for _ in range(t):
	(l, d, t) = [int(i) for i in input().split(' ')]
	r = modInverse(l, 1000000005, 1000000007)
	cosine = d * r % 1000000007
	matrix = [[2 * cosine, -1], [1, 0]]
	if t > 1:
		preMat = matrixPower(matrix, t - 1)
		ans = l * ((preMat[0][0] * cosine + preMat[0][1]) % 1000000007) % 1000000007
		print(ans)
	else:
		print(l * cosine % 1000000007)


MOD = 10 ** 9 + 7

def inverse(a):
	m = MOD
	(x, y) = (1, 0)
	while m > 1:
		(x, y) = (y, x - a // m * y)
		(a, m) = (m, a % m)
	if y < 0:
		y += MOD
	return y
mul = lambda a, b, x: ((a[0] * b[1] + a[1] * b[0] + 2 * x * a[0] * b[0]) % MOD, (a[1] * b[1] - a[0] * b[0]) % MOD)

def exp(a, k, x):
	ans = (0, 1)
	while k:
		if k & 1:
			ans = mul(ans, a, x)
		a = mul(a, a, x)
		k >>= 1
	return ans
T = int(input())
for _ in range(T):
	(l, d, t) = map(int, input().split())
	x = d * inverse(l) % MOD
	print(mul((x, -1), exp((1, 0), t - 1, x), x)[0] * l % MOD)