You are given the equation $\tan\alpha=\frac{p}{q}$ and a positive integer, $n$. Calculate $\tan n\alpha$. There are $\mathbf{T}$ test cases.

Input Format

The first line contains $\mathbf{T}$, the number of test cases. 

The next $\mathbf{T}$ lines contain three space separated integers: $p,q$ and $n$, respectively.  

Constraints 

$0\leq p\leq10^9$ 

$1\leq q\leq10^9$ 

$1\leq n\leq10^9$ 

$T\leq10^4$

Output Format

If the result is defined, it is always a rational number. However, it can be very big. 

Output the answer modulo $(10^9+7)$. 

If the answer is $\frac{a}{b}$ and $\boldsymbol{b}$ is not divisible by $(10^9+7)$, there is a unique integer $0\leq x<10^9+7$ where $a\equiv bx\quad\text{mod}\:(10^9+7)$. 

Output this integer, $\boldsymbol{x}$. 

It is guaranteed that $\boldsymbol{b}$ is not divisible by $(10^9+7)$ for all test cases.  

Sample Input
2
2 1 2
5 6 7

Sample Output
666666670
237627959

Explanation

If $\tan\alpha=\frac{2}{1}$ then $\tan2\alpha=-\frac{4}{3}$ and 
$-4\equiv3\times666667670\mod(10^9+7)$. 

So, the answer is $\boldsymbol{66666670}$.

Difficulty: EASY
Tags: Matrices

Starter code:

Solutions:
read = lambda : map(int, input().split())
P = 10 ** 9 + 7

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

def my_pow(a, b):
	ret = (1, 0)
	while b > 0:
		if b & 1 == 1:
			ret = mul(ret, a)
		a = mul(a, a)
		b >>= 1
	return ret
(n,) = read()
for _ in range(n):
	(p, q, n) = read()
	a = my_pow((q, p), n)
	print(a[1] * pow(a[0], P - 2, P) % P)


import sys
set
T = int(input())
MOD = 1000000007

def xgcd(a, b):
	if b == 0:
		return (a, 1, 0)
	(r_, u_, v_) = xgcd(b, a % b)
	(r, u, v) = (r_, v_, u_ - a // b * v_)
	return (r, u, v)

def tan(n, p, q):
	if n == 0:
		return (0, 1)
	if n % 2 == 0:
		(a, b) = tan(n // 2, p, q)
		return (2 * a * b % MOD, (b ** 2 - a ** 2) % MOD)
	else:
		(a, b) = tan(n - 1, p, q)
		return ((p * b + q * a) % MOD, (q * b - p * a) % MOD)
for t in range(T):
	(p, q, n) = tuple(map(int, input().split()))
	(a, b) = tan(n, p, q)
	(_, u, _) = xgcd(b, MOD)
	u = u * a % MOD
	print(u % MOD)


P = 1000000007

def inv(x):
	return pow(x, P - 2, P)

def tg2n(x):
	return 2 * x % P * inv(1 - x ** 2) % P

def tgp1(x, v0):
	return (x + v0) % P * inv(1 - x * v0) % P

def tang(n, v0):
	if n == 1:
		return v0
	x = tang(n // 2, v0)
	if n % 2 == 0:
		return tg2n(x)
	else:
		return tgp1(tg2n(x), v0)
T = int(input())
for t in range(T):
	(p, q, n) = list(map(int, input().split()))
	v0 = p * inv(q) % P
	print(tang(n, v0))


cases = int(input().strip())
m = 10 ** 9 + 7

def invMod(x):
	return (m + pow(x, m - 2, m)) % m

def tanMod(n, val):
	if n == 0:
		return 0
	elif n == 1:
		return val
	ret = tanMod(n // 2, val)
	ret = 2 * ret * invMod(1 - ret * ret) % m
	if n % 2 == 1:
		ret = (ret + val) * invMod(1 - ret * val) % m
	return ret
for x in range(cases):
	(p, q, n) = [int(x) for x in input().strip().split()]
	p = p * invMod(q) % m
	print(tanMod(n, p))


__author__ = 'Ward'

def inverse(a, p):
	return pow(a, p - 2, p)

def sumOfTangents(a, b, p):
	return (a + b) * inverse(1 - a * b, p) % p
M = 10 ** 9 + 7
T = int(input())
for x in range(0, T):
	(p, q, n) = map(int, input().split())
	a = p * inverse(q, M) % M
	ans = 0
	while n:
		if n % 2:
			ans = sumOfTangents(ans, a, M)
		a = sumOfTangents(a, a, M)
		n = int(n / 2)
	print(ans)


P = 10 ** 9 + 7

class Cmod:

	def __init__(self, re, im):
		(self.re, self.im) = (re, im)

	def __mul__(self, other):
		r = self.re * other.re - self.im * other.im
		i = self.re * other.im + self.im * other.re
		return Cmod(r % P, i % P)

	def __pow__(self, n):
		try:
			return [Cmod(1, 0), self, self * self][n]
		except IndexError:
			(half, odd) = divmod(n, 2)
			return (self ** 2) ** half * self ** odd
for test in range(int(input())):
	(p, q, n) = map(int, input().split())
	pqn = Cmod(q, p) ** n
	(qn, pn) = (pqn.re, pqn.im)
	print(pn * pow(qn, P - 2, P) % P)


from fractions import Fraction as f
import math
mod = 10 ** 9 + 7

def xbyymod(x, y):
	return x % mod * pow(y, mod - 2, mod) % mod

def tan(n, k):
	if n == 1:
		return k
	if n % 2 == 0:
		x = tan(n // 2, k)
		res = 2 * x * pow(1 - x * x, mod - 2, mod)
	else:
		y = tan(n - 1, k)
		res = (k + y) * pow(1 - k * y, mod - 2, mod)
	return res % mod

def main():
	t = int(input())
	for _ in range(t):
		(p, q, n) = map(int, input().split())
		a = p * pow(q, mod - 2, mod) % mod
		res = tan(n, a)
		print(res)
main()


from math import sqrt, cos, sin
m = int(1000000000.0 + 7)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m

def prod(f, g):
	return ((f[0] * g[0] - f[1] * g[1]) % m, (f[0] * g[1] + f[1] * g[0]) % m)

def modexp(a, mm):
	if mm == 0:
		return (1, 0)
	elif mm == 1:
		return a
	elif mm % 2 == 1:
		return prod(modexp(a, mm - 1), a)
	else:
		h = modexp(a, mm // 2)
		return prod(h, h)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	size = (p ** 2 + q ** 2) % m
	pos = (q, p)
	neg = (q, -p)
	b = int(2 * modexp(neg, n)[0]) % m
	a = int(2 * modexp(pos, n)[1]) % m
	inv = int(modinv(b, m))
	print(int(a) * inv % m)


mod = 10 ** 9 + 7

class fraction:
	p = 0
	q = 0

	def __init__(self, p1, q1):
		self.p = p1
		self.q = q1
		self.reduce()

	def reduce(self):
		gcd1 = gcd(self.p, self.q)
		self.p = self.p // gcd1
		self.q = self.q // gcd1

	def negate(self):
		return fraction(-self.p, self.q)

	def rec(self):
		return fraction(self.q, self.p)

	def add(self, frac):
		q = lcm(self.q, frac.q)
		p1 = self.p * q // self.q
		p2 = frac.p * q // frac.q
		return fraction(p1 + p2, q)

	def sub(self, frac):
		return self.add(frac.negate())

	def mult(self, frac):
		return fraction(self.p * frac.p, self.q * frac.q)

	def div(self, frac):
		return self.mult(frac.rec())

	def toString(self):
		return str(self.p) + '/' + str(self.q)

	def modu(self):
		return fraction(bez(mod, self.q)[1] * self.p % mod, 1)

def gcd(a, b):
	r = a % b
	while r != 0:
		a = b
		b = r
		r = a % b
	return b

def bez(a, b):
	(s1, s2, t1, t2, r1, r2) = (0, 1, 1, 0, b, a)
	while r1 != 0:
		q = r2 // r1
		(r2, r1) = (r1, r2 - q * r1)
		(s2, s1) = (s1, s2 - q * s1)
		(t2, t1) = (t1, t2 - q * t1)
	return (s2, t2, r2)

def lcm(a, b):
	return a * b // gcd(a, b)

def tan2a(frac):
	return fraction(2, 1).mult(frac).div(fraction(1, 1).sub(frac.mult(frac)))

def tanAdd(a, b):
	return a.add(b).div(fraction(1, 1).sub(a.mult(b)))

def binary(a):
	ar = []
	while a != 0:
		ar.append(a & 1)
		a = a >> 1
	return ar

def tanMult(a, b):
	bin = binary(a)
	tot = 0
	sum = 0
	for x in bin:
		if sum == 0:
			sum = b.modu()
		else:
			sum = tan2a(sum).modu()
		if x == 1:
			if tot == 0:
				tot = sum.modu()
			else:
				tot = tanAdd(sum, tot).modu()
	return tot
n = int(input())
for x in range(n):
	str = input().split()
	frac = tanMult(int(str[2]), fraction(int(str[0]), int(str[1])))
	print(frac.p)


from fractions import Fraction
N = 1000000007

def extended_gcd(a, b):
	if a < b:
		(a, b) = (b, a)
		swapped = True
	(s, old_s) = (0, 1)
	(t, old_t) = (1, 0)
	(r, old_r) = (b, a)
	while r != 0:
		quotient = int(old_r / r)
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	if not swapped:
		return (old_r, old_s, old_t)
	else:
		return (old_r, old_t, old_s)

def tanab(pa, qa, pb, qb):
	return ((pa * qb + pb * qa) % N, (qa * qb - pa * pb) % N)

def tanna(p, q, n):
	if n == 1:
		return (p, q)
	else:
		(p_half, q_half) = tanna(p, q, int(n / 2))
		tan_floor = tanab(p_half, q_half, p_half, q_half)
		if n % 2 == 0:
			return tan_floor
		else:
			return tanab(tan_floor[0], tan_floor[1], p, q)

def main():
	T = int(input())
	for i in range(T):
		(p, q, n) = [int(x) for x in input().strip().split(' ')]
		(a, b) = tanna(p, q, n)
		if b < 0:
			(a, b) = (-a, -b)
		(r, s, t) = extended_gcd(b, N)
		temp = a * s % N
		print(temp)
	return 0
main()


import math

def eea(a, b):
	(x, y, u, v) = (0, 1, 1, 0)
	while a != 0:
		(q, r) = (b // a, b % a)
		(m, n) = (x - u * q, y - v * q)
		(b, a, x, y, u, v) = (a, r, u, v, m, n)
	gcd = b
	return (gcd, x, y)

def modulo_inverse(b, m):
	(g, x, y) = eea(b, m)
	return x % m

class C:

	def __init__(self, real, imag):
		self.r = real
		self.i = imag

	def mult(self, other):
		return C((self.r * other.r - self.i * other.i) % (10 ** 9 + 7), (self.r * other.i + self.i * other.r) % (10 ** 9 + 7))

	def add(self, other):
		return C(self.r + other.r, self.i + other.i)

def n_tan(n, p, q):
	a = C(q, -p)
	found = {}
	found[1] = a
	i = 1
	while i < n:
		temp = found[i].mult(found[i])
		found[2 * i] = temp
		i *= 2
	ans = C(1, 0)
	guide = reversed(bin(n)[2:])
	for (j, digit) in enumerate(guide):
		if digit == '0':
			continue
		ans = ans.mult(found[2 ** j])
	num = -1 * ans.i
	den = ans.r
	if den < 0:
		den *= -1
		num *= -1
	g = eea(abs(num), abs(den))[0]
	num /= g
	den /= g
	return (round(num), round(den))
T = int(input())
for i in range(T):
	temp = input().strip().split()
	temp = [int(j) for j in temp]
	(p, q, n) = (temp[0], temp[1], temp[2])
	f = n_tan(n, p, q)
	inv = modulo_inverse(f[1], 10 ** 9 + 7)
	top = f[0]
	while top < 0:
		top += 10 ** 9 + 7
	ans = top * inv
	print(ans % (10 ** 9 + 7))


mod = 10 ** 9 + 7

def complex_mult(z1, z2):
	tmp = [0, 0]
	tmp[0] = z1[0] * z2[0] - z1[1] * z2[1]
	tmp[1] = z1[0] * z2[1] + z1[1] * z2[0]
	tmp[0] = tmp[0] % mod
	tmp[1] = tmp[1] % mod
	return tmp

def complex_pow(z, n):
	if n == 1:
		return z
	tmp1 = complex_pow(z, n // 2)
	tmp = complex_mult(tmp1, tmp1)
	if n % 2 == 1:
		tmp = complex_mult(tmp, z)
	return tmp

def egcd(a, b):
	(x, y, u, v) = (0, 1, 1, 0)
	while a != 0:
		(q, r) = (b // a, b % a)
		(m, n) = (x - u * q, y - v * q)
		(b, a, x, y, u, v) = (a, r, u, v, m, n)
	gcd = b
	return (gcd, x, y)

def modinv(a, m):
	(gcd, x, y) = egcd(a, m)
	return x % m
t = int(input())
for test in range(t):
	(p, q, n) = map(int, input().split())
	z = [q, p]
	z = complex_pow(z, n)
	a = z[1]
	b = z[0]
	if b < 0:
		b = -b
		a = -a
	x = modinv(b, mod) * a % mod
	print(x)


modo = 10 ** 9 + 7

def tanadd(a, b, p, q):
	return ((a * q + p * b) % modo, pow(pow(b * q - a * p, modo - 2, modo), modo - 2, modo))

def tandbl(p, q):
	return (2 * p * q, pow(pow(q * q - p * p, modo - 2, modo), modo - 2, modo))

def tanmul(p, q, n):
	if n == 1:
		return (p, q)
	(a, b) = tanmul(p, q, n >> 1)
	(a, b) = tandbl(a, b)
	if n & 1:
		(a, b) = tanadd(a, b, p, q)
	return (a % modo, pow(pow(b, modo - 2, modo), modo - 2, modo))
for _ in range(int(input().strip())):
	(p, q, n) = list((int(i) for i in input().strip().split()))
	(x, y) = tanmul(p, q, n)
	y = pow(y, modo - 2, modo)
	print(x * y % modo)


mod = int(1000000000.0 + 7)
t = int(input())

def inverse(a, b):
	return a * pow(b, mod - 2, mod) % mod
while t:
	t -= 1
	(a, b, n) = input().split()
	a = int(a)
	b = int(b)
	n = int(n)
	if n == 1:
		print(inverse(a, b))
		continue
	cur = inverse(a, b)
	a = [0] * 32
	a[0] = cur
	ans = -1
	if n & 1:
		ans = cur
	for i in range(1, 32):
		a[i] = inverse(-2 * a[i - 1], a[i - 1] ** 2 - 1)
		if 2 ** i & n:
			if ans == -1:
				ans = a[i]
			else:
				ans = inverse(-(a[i] + ans), a[i] * ans - 1)
	print(ans)


def read_int():
	return int(input().strip())

def read_ints():
	return [int(x) for x in input().strip().split(' ')]
MODULUS = 10 ** 9 + 7
INV_MOD = MODULUS - 2

def multiply(a, b):
	v0 = (a[0] * b[0] - a[1] * b[1]) % MODULUS
	v1 = (a[0] * b[1] + a[1] * b[0]) % MODULUS
	return (v0, v1)

def power(a, b):
	pw = (1, 0)
	while b > 0:
		if b % 2 == 1:
			pw = multiply(pw, a)
		a = multiply(a, a)
		b >>= 1
	return pw
T = read_int()
for t in range(T):
	(p, q, n) = read_ints()
	a = power((q, p), n)
	sol = a[1] * pow(a[0], INV_MOD, MODULUS) % MODULUS
	print(sol)


import sys

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b:
		(a, b) = (b, a % b)
	return a

def modinv(a, m):

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

def solve(p, q, n, m):
	if n == 0:
		return 0
	cache = []
	while n != 1:
		if n % 2:
			n -= 1
			cache.append('+1')
		else:
			cache.append('*2')
			n //= 2
	cache = cache[::-1]
	print('cache=%s' % cache, file=sys.stderr)
	(r, t) = (p, q)
	for op in cache:
		print('r=%d t=%d' % (r, t), file=sys.stderr)
		if op == '+1':
			(r, t) = (r * q + t * p, t * q - r * p)
		else:
			(r, t) = (2 * r * t, t * t - r * r)
		if t < 0:
			(r, t) = (-r, -t)
		(r, t) = (r * modinv(t, m) % m, 1)
	(a, b) = (r, t)
	print('a=%d b=%d' % (a, b), file=sys.stderr)
	c = modinv(b, m)
	print('c=%d' % c, file=sys.stderr)
	rval = a * c % m
	return rval
m = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	(p, q, n) = map(int, input().strip().split())
	print(solve(p, q, n, m))


mat_mul = lambda A, B: [[sum(map(int.__mul__, row, col)) % 1000000007 for col in zip(*B)] for row in A]
mat_pow = lambda A, n: A if n == 1 else mat_mul(A, A) if n == 2 else mat_mul(A, mat_pow(mat_pow(A, n // 2), 2)) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print(*((lambda p, q: p * pow(q, 1000000005, 1000000007) % 1000000007)(*(lambda p, q, n: mat_pow([[q, p], [-p, q]], n)[0][::-1])(*map(int, input().split()))) for _ in range(int(input()))), sep='\n')


def tan_n_alpha(p, q, n, m):
	s = 0
	t = 1
	while n:
		if n & 1:
			(s, t) = ((p * t + q * s) % m, (q * t - p * s) % m)
		n >>= 1
		if not n:
			break
		(p, q) = (2 * p * q % m, (q * q - p * p) % m)
	return (s, t)

def main():
	m = 10 ** 9 + 7
	for i in range(int(input())):
		(p, q, n) = map(int, input().split())
		(s, t) = tan_n_alpha(p, q, n, m)
		print(s * pow(t, m - 2, m) % m)
main()


import fractions

def gcd(a, b):
	x = 0
	y = 1
	u = 1
	v = 0
	while a != 0:
		q = b // a
		r = b % a
		m = x - u * q
		n = y - v * q
		b = a
		a = r
		x = u
		y = v
		u = m
		v = n
	g = b
	return (g, x, y)

def inverseModulo(a, m):
	(g, x, y) = gcd(a, m)
	return x % m

def computeTangent(n, m, tangents):
	if n in tangents:
		return tangents[n]
	k = n // 2
	tanK = computeTangent(k, m, tangents)
	if n % 2 == 0:
		tanN = [2 * tanK[0] * tanK[1] % m, (tanK[1] * tanK[1] - tanK[0] * tanK[0]) % m]
	else:
		tanK1 = computeTangent(k + 1, m, tangents)
		tanN = [(tanK1[0] * tanK[1] + tanK1[1] * tanK[0]) % m, (tanK1[1] * tanK[1] - tanK1[0] * tanK[0]) % m]
	tangents[n] = tanN
	return tanN
m = 1000000007
T = int(input())
for i in range(T):
	(p, q, n) = map(int, input().split())
	if n == 0:
		print(0)
		continue
	tangents = dict()
	tangents[1] = [p % m, q % m]
	t = computeTangent(n, m, tangents)
	aInv = inverseModulo(t[0], m)
	print(inverseModulo(aInv * t[1] % m, m))


from fractions import gcd
M = 10 ** 9 + 7

def add(r, s):
	return (r + s) * pow(1 - r * s, M - 2, M) % M

def compute(p, q, n):
	x = 0
	r = p * pow(q, M - 2, M) % M
	while n > 0:
		if n % 2 == 1:
			x = add(x, r)
		r = add(r, r)
		n //= 2
	return x
T = int(input())
for t in range(T):
	(p, q, n) = [int(y) for y in input().split()]
	print(compute(p, q, n))


import math
dic = {}

def prev2(x):
	return 2 ** int(math.log2(x))

def rtan(a, b, n):
	if (a, b, n) in dic:
		return dic[a, b, n]
	if n == 1:
		return (a, b)
	else:
		p = prev2(n)
		if p == n:
			p = p // 2
		q = n - p
		f = rtan(a, b, p)
		g = rtan(a, b, q)
		dic[a, b, n] = ((f[0] * g[1] + f[1] * g[0]) % 1000000007, (-1 * f[0] * g[0] + f[1] * g[1]) % 1000000007)
		return dic[a, b, n]
for _ in range(0, int(input())):
	(a, b, c) = map(int, input().split())
	f = rtan(a, b, c)
	ans = f[0] * pow(f[1], 1000000005, 1000000007) % 1000000007
	print(ans)


M = 1000000007

def tanplus(a, b, c, d):
	p = (a * d + b * c) % M
	q = (b * d + (M - a) * c) % M
	return (p, q)

def ntan(p, q, n):
	if n == 1:
		return (p, q)
	(a, b) = ntan(p, q, n // 2)
	(a, b) = tanplus(a, b, a, b)
	if n % 2 != 0:
		(a, b) = tanplus(a, b, p, q)
	return (a, b)

def fastexp(a, n, m):
	if n == 1:
		return a
	res = fastexp(a, n // 2, m)
	res *= res
	res %= m
	if n % 2 != 0:
		res *= a
		res %= m
	return res
T = int(input())
for _ in range(T):
	(p, q, n) = map(int, input().split())
	(a, b) = ntan(p, q, n)
	binv = fastexp(b, M - 2, M)
	res = a * binv % M
	print(res)


m = 10 ** 9 + 7
T = int(input())
for t in range(T):
	(p, q, n) = map(int, input().split())
	i = 0
	while n >> i > 1:
		i += 1
	r = p
	s = q
	while i:
		i -= 1
		(r, s) = (2 * r * s % m, (s * s - r * r) % m)
		if n >> i & 1:
			(r, s) = ((r * q + p * s) % m, (s * q - r * p) % m)
	print(r * pow(s, m - 2, m) % m)


def modI_euclid(a, z):
	(t, newt) = (0, 1)
	(r, newr) = (z, a)
	while newr:
		q = r // newr
		(t, newt) = (newt, t - q * newt)
		(r, newr) = (newr, r - q * newr)
	if t < 0:
		t += z
	return t

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if a == 0:
		return b
	b %= a
	if b == 0:
		return a
	else:
		return gcd(b, a)

def short(a, b):
	if a * b == 0:
		if a + b == 0:
			pass
		elif a == 0:
			b = b // abs(b)
		else:
			a = a // abs(a)
		return (a, b)
	else:
		c = max(1, gcd(abs(a), abs(b)))
		sgn = 1
		if a * b < 0:
			sgn = -1
		a = abs(a) // c
		b = abs(b) // c
		return (sgn * a, b)

def tanC(p, q, n):
	if p == 0:
		return (0, 1)
	sgn = 1
	if p * q < 0:
		sgn = -1
		p = abs(p)
		q = abs(q)
	if n == 1:
		return short(sgn * p, q)
	(x, y) = tanC(sgn * p, q, n // 2)
	(sgn, xx, yy) = (1, 2 * x * y, y * y - x * x)
	if xx * yy < 0:
		sgn = -1
	xx = abs(xx)
	yy = abs(yy)
	if n % 2 == 0:
		return short(sgn * (xx % z), yy % z)
	(x, y) = (sgn * xx, yy)
	(pp, qq, sgn) = (p * y + q * x, q * y - p * x, 1)
	if pp * qq < 0:
		sgn = -1
	pp = abs(pp)
	qq = abs(qq)
	return short(sgn * (pp % z), qq % z)
z = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(p, q, n) = map(int, input().strip().split())
	x = tanC(p, q, n)
	print(x[0] * modI_euclid(x[1], z) % z)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def tan_n_alpha_mod(n, r, mod):
	if n == 0:
		return 0
	elif n == 1:
		return r
	elif n % 2 == 0:
		t = tan_n_alpha_mod(n // 2, r, mod)
		return 2 * t * pow_mod(1 - t * t, mod - 2, mod) % mod
	else:
		t = tan_n_alpha_mod(n - 1, r, mod)
		return (t + r) * pow_mod(1 - t * r, mod - 2, mod) % mod
mod = pow(10, 9) + 7
T = int(input())
for _ in range(0, T):
	(p, q, n) = [int(a) for a in input().split()]
	print(tan_n_alpha_mod(n, p * pow_mod(q, mod - 2, mod) % mod, mod))


m = 10 ** 9 + 7

def solve(n, x, y):
	if n == 0:
		return (0, 1)
	if n & 1:
		(l, r) = solve(n - 1, x, y)
		return ((r * x + l * y) % m, (r * y - l * x) % m)
	(l, r) = solve(n // 2, x, y)
	return (2 * l * r % m, (r * r - l * l) % m)
for _ in range(int(input())):
	(l, r, n) = list(map(int, input().split()))
	(l, r) = solve(n, l, r)
	print(l * pow(r, m - 2, m) % m)


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

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 calc(p, q, n):
	M = 1000000007
	s = 0
	t = p * modinv(q, M) % M
	while n > 0:
		if n & 1:
			a = (s + t) % M
			b = (1 - s * t) % M
			s = a * modinv(b, M) % M
		a = (t + t) % M
		b = (1 - t * t) % M
		t = a * modinv(b, M) % M
		n >>= 1
	return s
T = int(input())
for i in range(T):
	[p, q, n] = input().split()
	[p, q, n] = [int(p), int(q), int(n)]
	print(calc(p, q, n))


MOD = 10 ** 9 + 7

class memoize(dict):

	def __init__(self, function):
		self.function = function

	def __call__(self, *args):
		return self[args]

	def __missing__(self, key):
		result = self[key] = self.function(*key)
		return result

def gcde(a, b):
	(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
	while r2 > 0:
		q = r // r2
		(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
	return (r, u, v)

def invMod(a, m):
	(r, u, v) = gcde(a, m)
	if r != 1:
		return None
	return u

@memoize
def solve(p, q, n):
	if n == 1:
		num = p
		den = q
	elif n % 2 == 0:
		num = 2 * solve(p, q, n // 2)
		den = 1 - solve(p, q, n // 2) ** 2
	else:
		num = solve(p, q, n - 1) + solve(p, q, 1)
		den = 1 - solve(p, q, n - 1) * solve(p, q, 1)
	return num * invMod(den, MOD) % MOD
T = int(input())
for _ in range(T):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


def tangente(x, y, p, q, mod):
	tan = [(x * q + y * p) % mod, (y * q - x * p) % mod]
	return tan

def pot(base, exp, mod):
	res = 1
	base = base % mod
	while exp > 0:
		if exp & 1:
			res = res * base % mod
		exp = exp >> 1
		base = base * base % mod
	return res
mod = 1000000007
t = int(input())
for c in range(t):
	(p, q, n) = map(int, input().strip().split())
	t = [p, q]
	tan = []
	tan.append(t)
	num = 2
	while num <= n:
		t = tangente(t[0], t[1], t[0], t[1], mod)
		tan.append(t)
		num = num * 2
	i = len(tan) - 1
	r = True
	rpta = [0, 1]
	while i >= 0 and r:
		if 2 ** i <= n:
			rpta = tangente(rpta[0], rpta[1], tan[i][0], tan[i][1], mod)
			n = n - 2 ** i
			if n == 0:
				r = False
		else:
			i = i - 1
	if rpta[0] < 0:
		rpta[0] *= -1
		rpta[1] *= -1
	potencia = pot(rpta[1], mod - 2, mod)
	ans = (rpta[0] + mod) % mod * potencia % mod
	print(ans)


from fractions import Fraction
MOD = 1000000007

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(a, m):
	(g, x, _) = egcd(a, m)
	assert g == 1
	return x % m
zero = Fraction(0)

def ntan(a, k):
	b = zero
	if k == 0:
		return b
	if k == 1:
		return a
	while k != 0:
		if k % 2 == 1:
			b = (a + b) / (1 - a * b)
			b = Fraction(b.numerator % MOD, b.denominator % MOD)
		a = 2 * a / (1 - a * a)
		a = Fraction(a.numerator % MOD, a.denominator % MOD)
		k //= 2
	return b
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	a = ntan(Fraction(p, q), n)
	print(a.numerator * modinv(a.denominator, MOD) % MOD)


read = lambda : map(int, input().split())
P = 10 ** 9 + 7

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

def my_pow(a, b):
	ret = (1, 0)
	while b > 0:
		if b & 1 == 1:
			ret = mul(ret, a)
		a = mul(a, a)
		b >>= 1
	return ret
(n,) = read()
for _ in range(n):
	(p, q, n) = read()
	a = my_pow((q, p), n)
	print(a[1] * pow(a[0], P - 2, P) % P)


mmm = 1000000007

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

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 tansum(a, b):
	n = (a + b) % mmm
	d = (1 - a * b) % mmm
	dinv = modinv(d, mmm)
	return n * dinv % mmm

def tann(a, b, n):
	binv = modinv(b, mmm)
	a = a * binv % mmm
	rv = 0
	while n > 0:
		if n & 1 == 1:
			rv = tansum(rv, a)
		a = tansum(a, a)
		n = n // 2
	return rv
num_probs = int(input())
for _ in range(num_probs):
	(a, b, n) = (int(x) for x in input().split())
	print(tann(a, b, n))


P = 10 ** 9 + 7

def inv_mod(n, p=P):
	return pow(n, p - 2, p)

def tan_mult_mod(t, n, p=P):
	if n == 0:
		return 0
	elif n % 2 == 0:
		t0 = tan_mult_mod(t, n // 2, p)
		return 2 * t0 * inv_mod(1 - t0 * t0) % p
	else:
		t0 = tan_mult_mod(t, n // 2, p)
		t1 = 2 * t0 * inv_mod(1 - t0 * t0) % p
		return (t + t1) * inv_mod(1 - t * t1) % p

def main():
	T = int(input())
	for _ in range(T):
		(p, q, n) = map(int, input().split())
		t = p * inv_mod(q) % P
		print(tan_mult_mod(t, n))
main()


def tan(n):
	if n == 1:
		return (p, q)
	else:
		if n % 2 == 0:
			(c, d) = tan(n // 2)
			x = 2 * c * d
			y = d * d - c * c
			c = x
			d = y
		else:
			(c, d) = tan(n // 2)
			x = 2 * c * d
			y = d * d - c * c
			c = q * x + p * y
			d = q * y - p * x
		c = c % m
		d = d % m
		return (c, d)
t = int(input())
l = {}
for i in range(t):
	(p, q, n) = map(int, input().split())
	if p == 0:
		print('0')
	else:
		m = 10 ** 9 + 7
		(a, b) = tan(n)
		print(a * pow(b, m - 2, m) % m)


from fractions import Fraction
M = 10 ** 9 + 7

def simple(t):
	return Fraction(t.numerator % M, t.denominator % M)

def tan(n, t):
	if n == 1:
		return t
	if n & 1:
		tx = tan(n - 1, t)
		return simple((tx + t) / (1 - tx * t))
	else:
		tx = tan(n // 2, t)
		return simple(2 * tx / (1 - tx * tx))
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	tx = Fraction(p, q)
	tnx = tan(n, tx)
	p = tnx.numerator % M
	q = tnx.denominator % M
	print(p * pow(q, M - 2, M) % M)


from fractions import Fraction
MOD = 1000000007

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(a, m):
	(_, x, _) = egcd(a, m)
	return x % m

def ntan(a, k):
	b = Fraction(0)
	if k == 0:
		return b
	if k == 1:
		return a
	while k != 0:
		if k % 2 == 1:
			b = (a + b) / (1 - a * b)
			b = Fraction(b.numerator % MOD, b.denominator % MOD)
		a = 2 * a / (1 - a * a)
		a = Fraction(a.numerator % MOD, a.denominator % MOD)
		k //= 2
	return b
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	a = ntan(Fraction(p, q), n)
	print(a.numerator * modinv(a.denominator, MOD) % MOD)


M = 1000000007

def fast_pow(base, n, M):
	if n == 0:
		return 1
	if n == 1:
		return base
	halfn = fast_pow(base, n // 2, M)
	if n % 2 == 0:
		return halfn * halfn % M
	else:
		return halfn * halfn % M * base % M

def findMMI_fermat(n, M):
	return fast_pow(n, M - 2, M)

def tan_add(a, b):
	return (a + b) * findMMI_fermat(1 - a * b, M) % M

def tan(n, t):
	if n == 1:
		return t
	elif n % 2 == 0:
		result = tan(n // 2, t)
		return tan_add(result, result)
	else:
		result = tan(n - 1, t)
		return tan_add(result, t)
import math
t = int(input())
for _ in range(0, t):
	(p, q, n) = map(int, input().split())
	p = (p + M) % M
	q = (q + M) % M
	k = p % 1000000007 * findMMI_fermat(q, 1000000007) % 1000000007 % 1000000007
	print(tan(n, k))


m = 10 ** 9 + 7

def moddiv(a, b):
	return a * pow(b, m - 2, m) % m

def tan(n, t):
	if n == 1:
		return t
	h = tan(n >> 1, t)
	h = moddiv(2 * h % m, (1 - h * h % m + m) % m)
	if n & 1:
		h = moddiv((h + t) % m, (1 - h * t % m + m) % m)
	return h
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	print(tan(n, moddiv(a, b)))


m = 10 ** 9 + 7

def solve(n, x, y):
	if n == 0:
		return (0, 1)
	if n & 1:
		(l, r) = solve(n - 1, x, y)
		return ((r * x + l * y) % m, (r * y - l * x) % m)
	(l, r) = solve(n // 2, x, y)
	return (2 * l * r % m, (r * r - l * l) % m)
for _ in range(int(input())):
	(l, r, n) = list(map(int, input().split()))
	(l, r) = solve(n, l, r)
	print(l * pow(r, m - 2, m) % m)


mod = int(1000000000.0 + 7)
t = int(input())

def inverse(a, b):
	return a * pow(b, mod - 2, mod) % mod
while t:
	t -= 1
	(a, b, n) = input().split()
	a = int(a)
	b = int(b)
	n = int(n)
	if n == 1:
		print(inverse(a, b))
		continue
	cur = inverse(a, b)
	a = [0] * 32
	a[0] = cur
	ans = -1
	if n & 1:
		ans = cur
	for i in range(1, 32):
		a[i] = inverse(-2 * a[i - 1], a[i - 1] ** 2 - 1)
		if 2 ** i & n:
			if ans == -1:
				ans = a[i]
			else:
				ans = inverse(-(a[i] + ans), a[i] * ans - 1)
	print(ans)


import os
import sys
from fractions import Fraction
MOD = 1000000007

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(a, m):
	(_, x, _) = egcd(a, m)
	return x % m

def ntan(a, k):
	b = Fraction(0)
	if k == 0:
		return b
	if k == 1:
		return a
	while k != 0:
		if k % 2 == 1:
			b = (a + b) / (1 - a * b)
			b = Fraction(b.numerator % MOD, b.denominator % MOD)
		a = 2 * a / (1 - a * a)
		a = Fraction(a.numerator % MOD, a.denominator % MOD)
		k //= 2
	return b
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	a = ntan(Fraction(p, q), n)
	print(a.numerator * modinv(a.denominator, MOD) % MOD)


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def fast_pow(base, n, M):
	if n == 0:
		return 1
	if n == 1:
		return base
	halfn = fast_pow(base, n // 2, M)
	if n % 2 == 0:
		return halfn * halfn % M
	else:
		return halfn * halfn % M * base % M

def findMMI_fermat(n, M):
	return fast_pow(n, M - 2, M)

def tan_add(a, b):
	return (a + b) * findMMI_fermat(1 - a * b, M) % M

def tan(n, t):
	if n == 1:
		return t
	elif n % 2 == 0:
		result = tan(n // 2, t)
		return tan_add(result, result)
	else:
		result = tan(n - 1, t)
		return tan_add(result, t)
import math
t = int(input())
for _ in range(0, t):
	(p, q, n) = map(int, input().split())
	p = (p + M) % M
	q = (q + M) % M
	k = p % 1000000007 * findMMI_fermat(q, 1000000007) % 1000000007 % 1000000007
	print(tan(n, k))


import os
import sys
M = 1000000007

def power(x, y):
	x %= M
	a = 1
	while y > 0:
		if y & 1 == 1:
			a = a * x % M
		x = x * x % M
		y >>= 1
	return a

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		s = (a + b) % M
		m = (1 - a * b % M + M) % M
		return s * power(m, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


import os
import sys
M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		st = (a + b) % M
		mj = (1 - a * b % M + M) % M
		return st * power(mj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


from fractions import Fraction
MOD = 1000000007

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(a, m):
	(_, x, _) = egcd(a, m)
	return x % m

def ntan(a, k):
	b = Fraction(0)
	if k == 0:
		return b
	if k == 1:
		return a
	while k != 0:
		if k % 2 == 1:
			b = (a + b) / (1 - a * b)
			b = Fraction(b.numerator % MOD, b.denominator % MOD)
		a = 2 * a / (1 - a * a)
		a = Fraction(a.numerator % MOD, a.denominator % MOD)
		k //= 2
	return b
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	a = ntan(Fraction(p, q), n)
	print(a.numerator * modinv(a.denominator, MOD) % MOD)


import os
import sys
M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


import os
import sys
M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


import os
import sys
M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


import os
import sys
M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))


from fractions import Fraction
MOD = 1000000007

def egcd(b, a):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while a != 0:
		(q, b, a) = (b // a, a, b % a)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(a, m):
	(_, x, _) = egcd(a, m)
	return x % m

def ntan(a, k):
	b = Fraction(0)
	if k == 0:
		return b
	if k == 1:
		return a
	while k != 0:
		if k % 2 == 1:
			b = (a + b) / (1 - a * b)
			b = Fraction(b.numerator % MOD, b.denominator % MOD)
		a = 2 * a / (1 - a * a)
		a = Fraction(a.numerator % MOD, a.denominator % MOD)
		k //= 2
	return b
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	a = ntan(Fraction(p, q), n)
	print(a.numerator * modinv(a.denominator, MOD) % MOD)


M = 1000000007

def power(x, y):
	x %= M
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % M
		x = x * x % M
		y >>= 1
	return ans

def tan(b, n):
	if n == 1:
		return b
	if n % 2 == 0:
		a = tan(b, n // 2)
		return 2 * a % M * power((1 - a ** 2 % M + M) % M, M - 2) % M
	else:
		a = tan(b, n - 1)
		soorat = (a + b) % M
		makhraj = (1 - a * b % M + M) % M
		return soorat * power(makhraj, M - 2) % M

def solve(p, q, n):
	return tan(p * power(q, M - 2) % M, n)
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(solve(p, q, n))