You're given three numbers: ${A}$, ${B}$, and $N$, and all you have to do is to find the number ${F}_N$ where 

$\begin{aligned}F_0&-A\\ F_1&=B\\ F_i&=F_{i-1}+F_{i-2}\:for\:i\geq2\end{aligned}$  

As the number can be very large, output it modulo $10^9+7$.  

Consider the following link: http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

Input Format

First line contains a single integer ${T}$ - the number of tests.
${T}$ lines follow, each containing three integers: ${A}$, ${B}$ and $N$.

Constraints

$1\leq T\leq1000$ 

$1\leq A,B,N\leq10^9$  

Output Format

For each test case output a single integer $-$ ${F}_N$.  

Sample Input
8  
2 3 1  
9 1 7  
9 8 3  
2 4 9  
1 7 2  
1 8 1  
4 3 1  
3 7 5  

Sample Output
3  
85  
25  
178  
8  
8  
3  
44

Explanation

First test case is obvious. 

Let's look through the second one: 

$F_{0}=9$ 

$F_1=1$ 

$F_2=1+9=10$ 

$F_3=10+1=11$ 

$F_4=11+10=21$ 

$F_5=21+11=32$ 

$F_6=32+21=53$ 

$F_7=53+32=85$

Difficulty: EASY
Tags: Number theory

Starter code:

Solutions:
mod = 1000000007

def mul(A, B):
	res = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			for h in range(2):
				res[i][j] = res[i][j] + A[i][h] * B[h][j]
				res[i][j] %= mod
	return res
t = int(input())
for i in range(t):
	(a, b, n) = map(int, input().split())
	res = [[1, 0], [0, 1]]
	x = [[0, 1], [1, 1]]
	while n:
		if n % 2 == 1:
			res = mul(res, x)
		x = mul(x, x)
		n //= 2
	print((res[0][0] * a + res[0][1] * b) % mod)


import sys
from math import sqrt
from decimal import *

def matmul(m1, m2, mod=0):
	rows = len(m1)
	cols = len(m2[0])
	size = len(m1[0])
	m = [[0] * cols for i in range(rows)]
	for r in range(rows):
		vec = m1[r]
		for c in range(cols):
			sum = 0
			for n in range(size):
				if vec[n] == 0:
					continue
				sum += vec[n] * m2[n][c]
			m[r][c] = sum if mod == 0 else sum % mod
	return m

def mat_I(size, frac=False):
	if not frac:
		m = [[0] * size for i in range(size)]
		for i in range(size):
			m[i][i] = 1
	else:
		m = [[Fraction(0)] * size for i in range(size)]
		for i in range(size):
			m[i][i] = Fraction(1)
	return m

def matexp(mat, n, mod=0):
	if n <= 0:
		return mat_I(len(mat))
	elif n == 1:
		return mat
	m = matexp(mat, n // 2, mod)
	m = matmul(m, m, mod)
	if n % 2 == 1:
		return matmul(m, mat, mod)
	else:
		return m

def matmulv(m1, v, mod=0):
	rows = len(m1)
	size = len(m1[0])
	m = [0] * rows
	for r in range(rows):
		vec = m1[r]
		sum = 0
		for n in range(size):
			sum += vec[n] * v[n]
		m[r] = sum if mod == 0 else sum % mod
	return m

def solve():
	stdin = sys.stdin
	T = int(stdin.readline())
	mat = [[0, 1], [1, 1]]
	MOD = 10 ** 9 + 7
	for _ in range(T):
		(a, b, n) = map(int, stdin.readline().split())
		mat2 = matexp(mat, n, MOD)
		vec = matmulv(mat2, [a, b], MOD)
		print(vec[0])
solve()


from sys import stderr
MOD = 10 ** 9 + 7

def main():
	ncases = int(input())
	for _ in range(ncases):
		(a, b, n) = [int(f) for f in input().split()]
		print(fibo(a, b, n))

def fibo(a, b, n):
	mtx = mtxpow([[1, 1], [1, 0]], n)
	print(mtx, file=stderr)
	return sum((u * v for (u, v) in zip(mtx[1], (b, a)))) % MOD

def mtxpow(mtx, n):
	if n == 1:
		return mtx
	sq = mtxtimes(mtx, mtx)
	ans = mtxpow(sq, n // 2)
	if n & 1:
		ans = mtxtimes(ans, mtx)
	return ans

def mtxtimes(a, b):
	return [[sum((a[i][j] * b[j][k] for j in range(len(b)))) % MOD for k in range(len(b[0]))] for i in range(len(a))]
main()


def f(n):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = f(n // 2)
		c = a * (b * 2 - a)
		d = a * a + b * b
		c %= 7 + 10 ** 9
		d %= 7 + 10 ** 9
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, c + d)
for i in range(int(input())):
	(x, y, n) = map(int, input().split())
	ans = f(n - 1)
	aa = x * ans[0] + y * ans[1]
	print(aa % (7 + 10 ** 9))


def findNthpower(M, n):
	if n == 1:
		return M
	R = findNthpower(M, n // 2)
	R = multiplymatrix(R, R)
	if n % 2 == 1:
		R = multiplymatrix(R, M)
	return R

def multiplymatrix(A, B):
	x = (A[0][0] * B[0][0] % 1000000007 + A[0][1] * B[1][0] % 1000000007) % 1000000007
	y = (A[0][0] * B[0][1] % 1000000007 + A[0][1] * B[1][1] % 1000000007) % 1000000007
	z = (A[1][0] * B[0][0] % 1000000007 + A[1][1] * B[1][0] % 1000000007) % 1000000007
	w = (A[1][0] * B[0][1] % 1000000007 + A[1][1] * B[1][1] % 1000000007) % 1000000007
	F = [[x, y], [z, w]]
	return F
t = int(input())
for _ in range(t):
	(f0, f1, n) = (int(x) for x in input().split())
	f2 = f0 + f1
	F = [[f2, f1], [f1, f0]]
	A = [[1, 1], [1, 0]]
	if n == 1:
		print(f1 % 1000000007)
		continue
	if n == 2:
		print(f2 % 1000000007)
		continue
	ApowerN = findNthpower(A, n)
	print(multiplymatrix(ApowerN, F)[1][1])


mod = 10 ** 9 + 7

def mult(a, b):
	res = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			res[i][j] = sum((x * y for (x, y) in zip(a[i], (c[j] for c in b)))) % mod
	return res

def get(n):
	a = [[1, 1], [1, 0]]
	res = [[1, 0], [0, 1]]
	while n:
		if n & 1:
			res = mult(res, a)
		a = mult(a, a)
		n //= 2
	return res

def solve():
	(a, b, n) = (int(x) for x in input().split())
	m = get(n)
	print((b * m[1][0] + a * m[1][1]) % mod)
t = int(input())
while t:
	solve()
	t -= 1


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


MOD = 10 ** 9 + 7

def matmod(mat, mod):
	return [[e % mod for e in row] for row in mat]

def matmult(mat1, mat2):
	return [[sum((mat1[r][i] * mat2[i][c] for i in range(len(mat2)))) for c in range(len(mat2))] for r in range(len(mat1))]

def matmultmod(mat1, mat2, mod):
	return matmod(matmult(mat1, mat2), mod)

def matexpmod(pow, mat, mod):
	if pow == 1:
		return mat
	rest = matexpmod(pow // 2, matmultmod(mat, mat, mod), mod)
	if pow % 2:
		return matmultmod(mat, rest, mod)
	else:
		return rest

def generalFibonacciMod(A, B, N, mod=MOD):
	Fmat = matexpmod(N, [[1, 1], [1, 0]], mod)
	return (Fmat[1][0] * B + Fmat[1][1] * A) % mod
num_tests = int(input())
for test in range(num_tests):
	(A, B, N) = map(int, input().split())
	print(generalFibonacciMod(A, B, N))


mod = 10 ** 9 + 7

def matMult(A, B):

	def val(i, j):
		return (A[i][0] * B[0][j] % mod + A[i][1] * B[1][j] % mod) % mod
	return [[val(0, 0), val(0, 1)], [val(1, 0), val(1, 1)]]

def matrixPower(A, n):
	if n == 0:
		return ((1, 0), (0, 1))
	if n % 2 == 1:
		return matMult(A, matrixPower(A, n - 1))
	root = matrixPower(A, n / 2)
	return matMult(root, root)

def fiboNumber(n, a, b):
	if n == 1:
		return b
	M = [[0, 1], [1, 1]]
	temp = matrixPower(M, n - 1)
	return (temp[1][0] * a % mod + temp[1][1] * b % mod) % mod

def main():
	mod = 10 ** 9 + 7
	t = int(input())
	for _ in range(t):
		(a, b, n) = map(int, input().split())
		mat = [[0, 1], [1, 1]]
		print(fiboNumber(n, a, b))
main()


from math import sqrt
p = 10 ** 9 + 7
A = [[1, 1], [1, 0]]
I = [[1, 0], [0, 1]]

def mul(A, B):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def exp(A, n):
	if n == 0:
		return I
	elif n == 1:
		return A
	elif n % 2 == 0:
		return exp(mul(A, A), n // 2)
	else:
		return mul(A, exp(mul(A, A), (n - 1) // 2))

def fib(a, b, n):
	An = exp(A, n)
	return (An[1][0] * b + An[1][1] * a) % p
cases = int(input())
for _ in range(cases):
	(a, b, n) = [int(x) for x in input().split()]
	print(fib(a, b, n))


MOD = 10 ** 9 + 7
cache = {}

def fib(n):
	if n <= 1:
		return n
	if n in cache:
		return cache[n]
	if n % 2 == 0:
		Fn = fib(n // 2)
		Fn1 = fib(n // 2 - 1)
		res = (2 * Fn1 + Fn) * Fn % MOD
	else:
		Fn = fib(n // 2 + 1)
		Fn1 = fib(n // 2)
		res = (Fn ** 2 + Fn1 ** 2) % MOD
	cache[n] = res
	return res

def fib2(a, b, n):
	if n == 0:
		return a
	if n == 1:
		return b
	expa = fib(n - 1)
	expb = fib(n)
	return (a * expa + b * expb) % MOD
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	print(fib2(a, b, n))


MOD = 1000000007

def fib(num):
	F = [[1, 1], [1, 0]]
	if num == 0:
		return 0
	F = power(F, num - 1)
	return F

def power(F, num):
	if num == 0 or num == 1:
		return
	M = [[1, 1], [1, 0]]
	power(F, int(num / 2))
	multiply(F, F)
	if num % 2 != 0:
		F = multiply(F, M)
	return F

def multiply(F, M):
	x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MOD
	y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MOD
	z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MOD
	w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MOD
	F[0][0] = x
	F[0][1] = y
	F[1][0] = z
	F[1][1] = w
	return F
for _ in range(int(input())):
	(A, B, N) = [int(i) for i in input().split()]
	if N == 0:
		print(A)
		continue
	elif N == 1:
		print(B)
		continue
	elif N == 2:
		print(A + B)
		continue
	else:
		matrix = fib(N)
		print((matrix[0][0] * B + matrix[0][1] * A) % MOD)


def findNthpower(M, n):
	if n == 1:
		return M
	R = findNthpower(M, n // 2)
	R = multiplymatrix(R, R)
	if n % 2 == 1:
		R = multiplymatrix(R, M)
	return R

def multiplymatrix(A, B):
	x = (A[0][0] * B[0][0] % 1000000007 + A[0][1] * B[1][0] % 1000000007) % 1000000007
	y = (A[0][0] * B[0][1] % 1000000007 + A[0][1] * B[1][1] % 1000000007) % 1000000007
	z = (A[1][0] * B[0][0] % 1000000007 + A[1][1] * B[1][0] % 1000000007) % 1000000007
	w = (A[1][0] * B[0][1] % 1000000007 + A[1][1] * B[1][1] % 1000000007) % 1000000007
	F = [[x, y], [z, w]]
	return F
t = int(input())
for _ in range(t):
	(f0, f1, n) = (int(x) for x in input().split())
	f2 = f0 + f1
	F = [[f2, f1], [f1, f0]]
	A = [[1, 1], [1, 0]]
	if n == 1:
		print(f1 % 1000000007)
		continue
	if n == 2:
		print(f2 % 1000000007)
		continue
	ApowerN = findNthpower(A, n)
	print(multiplymatrix(ApowerN, F)[1][1])


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


MOD = 1000000007

def fib(num):
	F = [[1, 1], [1, 0]]
	if num == 0:
		return 0
	F = power(F, num - 1)
	return F

def power(F, num):
	if num == 0 or num == 1:
		return
	M = [[1, 1], [1, 0]]
	power(F, int(num / 2))
	multiply(F, F)
	if num % 2 != 0:
		F = multiply(F, M)
	return F

def multiply(F, M):
	x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MOD
	y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MOD
	z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MOD
	w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MOD
	F[0][0] = x
	F[0][1] = y
	F[1][0] = z
	F[1][1] = w
	return F
for _ in range(int(input())):
	(A, B, N) = [int(i) for i in input().split()]
	if N == 0:
		print(A)
		continue
	elif N == 1:
		print(B)
		continue
	elif N == 2:
		print(A + B)
		continue
	else:
		matrix = fib(N)
		print((matrix[0][0] * B + matrix[0][1] * A) % MOD)


def eye(n):
	I = []
	for i in range(n):
		I.append([0] * n)
		I[i][i] = 1
	return I

def mul(A, B):
	M = []
	for i in range(len(A)):
		M.append([])
		for j in range(len(B[0])):
			M[i].append(sum((A[i][k] * B[k][j] for k in range(len(A[i])))))
	return M

def mod(A, m):
	M = []
	for i in range(len(A)):
		M.append([])
		for j in range(len(A[i])):
			M[i].append(A[i][j] % m)
	return M

def pow(A, e, m=None):
	P = eye(len(A))
	while e > 0:
		if e & 1:
			P = mul(P, A)
			if m:
				P = mod(P, m)
		A = mul(A, A)
		if m:
			A = mod(A, m)
		e >>= 1
	return P
MOD = 10 ** 9 + 7

def solve(A, B, N):
	M = mul(pow([[1, 1], [1, 0]], N, MOD), [[B], [A]])
	return M[1][0] % MOD
T = int(input())
for _ in range(T):
	(A, B, N) = (int(_) for _ in input().split())
	print(solve(A, B, N))


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


def power(a, n):
	if n == 1:
		return a
	x = power(a, int(n / 2))
	if n % 2 == 0:
		return matrixMul(x, x)
	else:
		return matrixMul(a, matrixMul(x, x))

def matrixMul(a, b):
	c = [[(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % 1000000007, (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % 1000000007], [(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % 1000000007, (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % 1000000007]]
	return c
t = int(input())
for i in range(0, t):
	ls = input().split()
	fibo = [int(ls[0]), int(ls[1])]
	n = int(ls[2])
	s = power([[1, 1], [1, 0]], n)
	print((fibo[1] * s[0][1] + fibo[0] * s[1][1]) % 1000000007)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


def mat_prod(m1, m2, mod):
	a = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % mod
	b = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % mod
	c = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % mod
	d = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % mod
	m = [[a, b], [c, d]]
	return m

def fib(a, b, n):
	res = [[1, 1], [1, 0]]
	x = [[1, 1], [1, 0]]
	c = pow(10, 9) + 7
	while n:
		if n & 1 == 1:
			res = mat_prod(res, x, c)
		x = mat_prod(x, x, c)
		n >>= 1
	return (res[1][0] * b + res[1][1] * a) % c

def main():
	t = int(input())
	for i in range(t):
		(a, b, n) = input().split()
		(a, b, n) = (int(a), int(b), int(n))
		print(fib(a, b, n - 1))
main()


M = 10 ** 9 + 7

def matMult(a, b):
	zip_b = list(zip(*b))
	return [[sum((e_a * e_b % M for (e_a, e_b) in zip(row_a, col_b))) % M for col_b in zip_b] for row_a in a]

def powMat(m, x):
	if x == 0:
		return [[1, 0], [0, 1]]
	if x == 1:
		return [row[:] for row in m]
	temp = powMat(m, x // 2)
	if x % 2 == 0:
		return matMult(temp, temp)
	else:
		return matMult(m, matMult(temp, temp))
t = int(input())
for _ in range(t):
	(a, b, n) = list(map(int, input().split()))
	fibM = [[1, 1], [1, 0]]
	m = powMat(fibM, n - 1)
	print((m[0][0] * b + m[0][1] * a) % M)


from fileinput import input

def find():
	lines = input()
	noc = [int(x) for x in lines[0].strip().split()][0]
	for i in range(1, noc + 1):
		(a, b, n) = [int(x) for x in lines[i].strip().split()]
		m = [[1, 1], [1, 0]]
		if n == 1:
			print(b, end='\n')
			continue
		mp = matrixPow(m, n - 1)
		(newa, newb) = mvProd(mp, [b, a])
		print(newa, end='\n')

def matrixPow(m, p):
	if p == 1:
		return m
	half = matrixPow(m, p // 2)
	tmp = matrixProd(half, half)
	if p & 1 == 0:
		return tmp
	else:
		return matrixProd(m, tmp)

def matrixProd(m, n):
	(a00, a01) = m[0]
	(a10, a11) = m[1]
	(b00, b01) = n[0]
	(b10, b11) = n[1]
	c00 = (a00 * b00 + a01 * b10) % 1000000007
	c01 = (a00 * b01 + a01 * b11) % 1000000007
	c10 = (a10 * b00 + a11 * b10) % 1000000007
	c11 = (a10 * b01 + a11 * b11) % 1000000007
	return [[c00, c01], [c10, c11]]

def mvProd(m, v):
	(a00, a01) = m[0]
	(a10, a11) = m[1]
	(a, b) = (v[0] % 1000000007, v[1] % 1000000007)
	newa = (a00 * a + a01 * b) % 1000000007
	newb = (a10 * a + a11 * b) % 1000000007
	return [newa, newb]
find()


def mulmod(A, B, p):
	return [(A[0] * B[0] + A[1] * B[2]) % p, (A[0] * B[1] + A[1] * B[3]) % p, (A[2] * B[0] + A[3] * B[2]) % p, (A[2] * B[1] + A[3] * B[3]) % p]

def powmod(A, n, p):
	res = [1, 0, 0, 1]
	bas = A
	if n == 0:
		return res
	while n > 0:
		if n % 2 == 1:
			res = mulmod(res, bas, p)
		bas = mulmod(bas, bas, p)
		n = n // 2
	return res

def fibo(A):
	p = 1000000007
	if A[2] < 2:
		return A[A[2]]
	F = powmod([1, 1, 1, 0], A[2] - 1, p)
	d = F[0] * A[1] + F[1] * A[0]
	return d % p
t = int(input())
for _ in range(t):
	A = [int(x) for x in input().split()]
	print(fibo(A))


def fib(n):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = fib(n // 2)
		c = a * (b * 2 - a) % (10 ** 9 + 7)
		d = (a * a + b * b) % (10 ** 9 + 7)
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, c + d)

def main():
	t = int(input())
	for _ in range(t):
		(a, b, n) = list(map(int, input().split()))
		(fn, fn1) = fib(n - 1)
		ans = (fn * (a + b) + (fn1 - fn) * b) % (10 ** 9 + 7)
		print(ans)
main()


def matrix_mult(A, B):
	(a, b, c, d) = A
	(e, f, g, h) = B
	return ((a * e + b * g) % 1000000007, (a * f + b * h) % 1000000007, (c * e + d * g) % 1000000007, (c * f + d * h) % 1000000007)

def power(A, n):
	result = (1, 0, 0, 1)
	while n > 0:
		if n % 2:
			result = matrix_mult(result, A)
		n >>= 1
		A = matrix_mult(A, A)
	return result

def fib(A, B, N):
	(final_a, final_b, final_c, final_d) = power((1, 1, 1, 0), N - 1)
	return (B * final_a % 1000000007 + A * final_b % 1000000007) % 1000000007

def main():
	t = int(input())
	for _ in range(t):
		(A, B, N) = [int(elem) for elem in input().split()]
		print(fib(A, B, N))
main()


MOD = 1000000007

def matrixMultiply(M, N):
	return [[sum((m * n for (m, n) in zip(M_row, N_col))) % MOD for N_col in zip(*N)] for M_row in M]

def matrixExponent(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		temp = matrixExponent(A, N // 2)
		temp = matrixMultiply(temp, temp)
		if N % 2 == 1:
			temp = matrixMultiply(temp, A)
	return temp
T = int(input())
for t in range(T):
	(A, B, N) = map(int, input().split())
	M = matrixExponent([[1, 1], [1, 0]], N)
	result = (M[1][0] * B + M[1][1] * A) % MOD
	print(result)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


fibonacciMemo = {}

def fibonacci(n):
	if n <= 0:
		return 0
	elif n == 1:
		return 1
	else:
		if not n in fibonacciMemo:
			if n % 2 == 0:
				fibonacciMemo[n] = (2 * fibonacci(n / 2 - 1) + fibonacci(n / 2)) * fibonacci(n / 2) % 1000000007
			elif n % 2 == 1:
				fibonacciMemo[n] = (fibonacci((n + 1) / 2) ** 2 + fibonacci((n + 1) / 2 - 1) ** 2) % 1000000007
		return fibonacciMemo[n]

def FibonacciEasy(a, b, n):
	if n == 0:
		return a
	elif n == 1:
		return b
	else:
		return (a * fibonacci(n - 1) + b * fibonacci(n)) % 1000000007
t = int(input())
for i in range(0, t):
	(a, b, n) = input().split()
	(a, b, n) = (int(a), int(b), int(n))
	res = FibonacciEasy(a, b, n)
	print(res)


MOD = 1000000007
from functools import reduce

def matrix_mult(a, b):
	return [(a[0] * b[0] + a[1] * b[2]) % MOD, (a[0] * b[1] + a[1] * b[3]) % MOD, (a[2] * b[0] + a[3] * b[2]) % MOD, (a[2] * b[1] + a[3] * b[3]) % MOD]
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	exponent = '{0:b}'.format(n - 1)
	n_powers = len(exponent)
	power_table = [0] * n_powers
	power_table[0] = [1, 1, 1, 0]
	for i in range(1, n_powers):
		power_table[i] = matrix_mult(power_table[i - 1], power_table[i - 1])
	mtp = reduce(matrix_mult, [power_table[i] for i in range(n_powers) if exponent[n_powers - i - 1] == '1'], [1, 0, 0, 1])
	print((mtp[0] * b + mtp[1] * a) % MOD)


M = 10 ** 9 + 7

def fibonacci(n):
	if n < 0:
		raise ValueError('Negative arguments not implemented')
	return _fib(n)

def _fib(n):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = _fib(n // 2)
		c = a * (b * 2 - a) % M
		d = (a * a + b * b) % M
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, c + d)
myFib = (0, 1)
for _ in range(int(input())):
	(a, b, n) = [int(ns) for ns in input().split()]
	if n == 1:
		print(b)
	else:
		(x, y) = fibonacci(n - 1)
		print((a * x + b * y) % M)


import fileinput
import math

class MatrixModulo:

	def __init__(self, a, b, c, d, m):
		self.a = a
		self.b = b
		self.c = c
		self.d = d
		self.modulo = m

	def multiply(self, B):
		return MatrixModulo((self.a * B.a + self.b * B.c) % self.modulo, (self.a * B.b + self.b * B.d) % self.modulo, (self.c * B.a + self.d * B.c) % self.modulo, (self.c * B.b + self.d * B.d) % self.modulo, self.modulo)

	def pow(self, p):
		if p == 1:
			return self
		if p % 2 == 1:
			return self.multiply(self.pow(p - 1))
		B = self.pow(p / 2)
		return B.multiply(B)

	def __str__(self):
		return '%d %d\n%d %d\n\n' % (self.a, self.b, self.c, self.d)

def fibonacci_m(a, b, n, m):
	if n == 0:
		return a
	if n == 1:
		return b
	R = MatrixModulo(1, 1, 1, 0, m).pow(n - 1)
	return (R.a * b + R.b * a) % m
count = 0
max = 1000
MAX = 10 ** 9 + 7
for line in fileinput.input():
	if count == 0:
		max = int(line)
		count = 1
		continue
	if count > max:
		break
	count += 1
	arr = line.split()
	print(fibonacci_m(int(arr[0]), int(arr[1]), int(arr[2]), MAX))


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


from sys import stdin
z = 1000000007

def fib(n, m={0: 0, 1: 1}):
	if n in m:
		return m[n]
	if n % 2 == 1:
		a = int((n + 1) / 2)
		b = a - 1
		m[a] = fib(a, m)
		m[b] = fib(b, m)
		m[n] = (m[a] * m[a] + m[b] * m[b]) % z
	else:
		a = int(n / 2)
		b = a - 1
		m[a] = fib(a, m)
		m[b] = fib(b, m)
		m[n] = (2 * m[b] + m[a]) * m[a] % z
	return m[n]
t = int(stdin.readline())
for ti in range(t):
	(a, b, n) = tuple((int(x) for x in stdin.readline().split()))
	if n == 0:
		print(a)
	else:
		print((a * fib(n - 1) + b * fib(n)) % z)


def matrixsquare(A, mod):
	return matmult1(A, A, mod)

def matmult1(A, B, mod):
	if mod is not None:
		return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod]]

def matmult2(A, B, mod):
	if mod is not None:
		return [(A[0][0] * B[0] + A[0][1] * B[1]) % mod, (A[1][0] * B[0] + A[1][1] * B[1]) % mod]

def matrixpow(M, power, mod):
	if int(power) <= 0:
		return M
	powers = list(reversed([True if i == '1' else False for i in bin(power)[2:]]))
	matrices = [None for _ in powers]
	matrices[0] = M
	for i in range(1, len(powers)):
		matrices[i] = matrixsquare(matrices[i - 1], mod)
	result = None
	for (matrix, power) in zip(matrices, powers):
		if power:
			if result is None:
				result = matrix
			else:
				result = matmult1(result, matrix, mod)
	return result
for i in range(1, int(input()) + 1):
	case = input()
	lst = case.split(' ')
	fibmatrix = [[1, 1], [1, 0]]
	nmatrix = matrixpow(fibmatrix, int(lst[2]), 10 ** 9 + 7)
	startmatrix = [int(lst[1]), int(lst[0])]
	res = matmult2(nmatrix, startmatrix, 10 ** 9 + 7)
	print(res[1])


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	I = [[1, 0], [0, 1]]
	if N == 0:
		return I
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
for T in range(int(input())):
	(A, B, N) = list(map(int, input().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


hell = 1000000007

def matrixMul(m1, m2):
	hell = 1000000007
	return [[(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % hell, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % hell], [(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % hell, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % hell]]

def matrixexp(m, n):
	identity = [[1, 0], [0, 1]]
	if n == 1:
		return m
	if n == 0:
		return identity
	t = n // 2
	x = matrixexp(m, t)
	if n & 1:
		return matrixMul(matrixMul(x, x), m)
	else:
		return matrixMul(x, x)

def f(A, B, N):
	if N == 0:
		return A
	if N == 1:
		return B
	t = [B, A]
	x = matrixexp([[1, 1], [1, 0]], N - 1)
	return (x[0][0] * B + x[0][1] * A) % hell
for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	print(f(A, B, N))


MOD = 10 ** 9 + 7

def mult22(a, b):
	x = a[0][0] * b[0][0] + a[0][1] * b[1][0]
	y = a[0][0] * b[0][1] + a[0][1] * b[1][1]
	u = a[1][0] * b[0][0] + a[1][1] * b[1][0]
	v = a[1][0] * b[0][1] + a[1][1] * b[1][1]
	a[0][0] = x % MOD
	a[0][1] = y % MOD
	a[1][0] = u % MOD
	a[1][1] = v % MOD
	return

def pow22(a, n):
	if n <= 1:
		return
	pow22(a, n // 2)
	mult22(a, a)
	if n % 2 != 0:
		mult22(a, [[1, 1], [1, 0]])
	return
for t in range(int(input())):
	(a, b, n) = list(map(int, input().split()))
	q = [[b, 0], [a, 0]]
	m = [[1, 1], [1, 0]]
	pow22(m, n)
	mult22(m, q)
	print(m[1][0])


def multip(X, Y):
	XY = [[(X[0][0] * Y[0][0] % 1000000007 + X[0][1] * Y[1][0] % 1000000007) % 1000000007, (X[0][0] * Y[0][1] % 1000000007 + X[0][1] * Y[1][1] % 1000000007) % 1000000007], [(X[1][0] * Y[0][0] % 1000000007 + X[1][1] * Y[1][0] % 1000000007) % 1000000007, (X[1][0] * Y[0][1] % 1000000007 + X[1][1] * Y[1][1] % 1000000007) % 1000000007]]
	return XY

def potencia(matrix, n):
	if n == 1:
		return matrix
	matrix = potencia(matrix, int(n / 2))
	matrix = multip(matrix, matrix)
	if n % 2 != 0:
		matrix = multip(matrix, matrix0)
	return matrix
T = int(input())
matrix0 = [[1, 1], [1, 0]]
for i in range(T):
	(A, B, N) = (int(x) for x in input().split())
	if N > 1:
		matrix = potencia(matrix0, N - 1)
		F = [B, A]
		print((matrix[0][0] * F[0] % 1000000007 + matrix[0][1] * F[1] % 1000000007) % 1000000007)
	else:
		print(B)


def matr_dot(m1, m2, m):
	y00 = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % m
	y01 = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % m
	y10 = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % m
	y11 = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % m
	return [[y00, y01], [y10, y11]]

def matrix_pow_mod(A, p, m):
	if p == 1:
		return A
	if p % 2 == 1:
		return matr_dot(A, matrix_pow_mod(A, p - 1, m), m)
	B = matrix_pow_mod(A, p / 2, m)
	return matr_dot(B, B, m)

def fibo3(a, b, n, m):
	if n == 0:
		return a
	if n == 1:
		return b
	f1 = [b, a]
	matrA = [[1, 1], [1, 0]]
	matr1 = matrix_pow_mod(matrA, n - 1, m)
	res = matr1[0][0] * f1[0] + matr1[0][1] * f1[1]
	return res % m
nTst = int(input())
inp = []
for i1 in range(nTst):
	inp.append(input())
m1 = 1000000007
for t1 in range(nTst):
	x1 = list(map(int, inp[t1].split()))
	a1 = x1[0]
	b1 = x1[1]
	nn = x1[2]
	print(fibo3(a1, b1, nn, m1))


from functools import lru_cache
MOD = 10 ** 9 + 7
id = ((1, 0), (0, 1))
fib_trans = ((0, 1), (1, 1))

def mmul(A, B, mod):
	return (((A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod), ((A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod))

@lru_cache(maxsize=None)
def mpow(A, n, mod):
	if n == 0:
		return id
	elif n % 2 == 0:
		tmp = mpow(A, n // 2, mod)
		return mmul(tmp, tmp, mod)
	else:
		return mmul(mpow(A, n - 1, mod), A, mod)
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	trans = mpow(fib_trans, n, MOD)
	print((trans[0][0] * a + trans[0][1] * b) % MOD)


from math import log

def dotProd(u, v, m):
	return (u[0] * v[0] % m + u[1] * v[1] % m) % m

def matProd(a, b, m):
	return [[dotProd(a[0], [v[0] for v in b], m), dotProd(a[0], [v[1] for v in b], m)], [dotProd(a[1], [v[0] for v in b], m), dotProd(a[1], [v[1] for v in b], m)]]

def matVecProd(a, v, m):
	return [dotProd(a[0], v, m), dotProd(a[1], v, m)]

def matPow(a, n, m):
	r = int(log(n) / log(2))
	prod = [[1, 0], [0, 1]]
	n0 = n
	for i in range(r + 1):
		prod = matProd(prod, prod, m)
		d = n0 // 2 ** (r - i)
		if d == 1:
			prod = matProd(prod, a, m)
		n0 -= d * 2 ** (r - i)
	return prod
t = int(input())
f = [[1, 1], [1, 0]]
p = 10 ** 9 + 7
for _ in range(t):
	(a, b, n) = [int(x) for x in input().split()]
	fn = matPow(f, n, p)
	v = matVecProd(fn, [b, a], p)
	print(v[1])


from time import time

def fib(n, a, b):
	f = [[1, 1], [1, 0]]
	if n == 0:
		return a
	if n == 1:
		return b
	power(f, n - 1)
	val = (f[0][0] * b + f[0][1] * a) % mod
	return val

def power(f, n):
	if n > 1:
		m = [[1, 1], [1, 0]]
		power(f, n // 2)
		multiply(f, f)
		if n % 2 == 1:
			multiply(f, m)

def multiply(f, m):
	x = f[0][0] * m[0][0] + f[0][1] * m[1][0]
	y = f[0][0] * m[0][1] + f[0][1] * m[1][1]
	z = f[1][0] * m[0][0] + f[1][1] * m[1][0]
	w = f[1][0] * m[0][1] + f[1][1] * m[1][1]
	x %= mod
	y %= mod
	z %= mod
	w %= mod
	f[0][0] = x
	f[0][1] = y
	f[1][0] = z
	f[1][1] = w
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(a, b, n) = (int(x) for x in input().split())
	print(fib(n, a, b))


t = int(input())

def mul(A, B):
	C = [[0, 0], [0, 0]]
	C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % 1000000007
	C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % 1000000007
	C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % 1000000007
	C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % 1000000007
	return C

def pow(A, n):
	if n == 1:
		return A
	if n % 2 == 1:
		return mul(A, pow(A, n - 1))
	C = pow(A, n / 2)
	return mul(C, C)

def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	F = [[1, 1], [1, 0]]
	C = pow(F, n - 1)
	return C[0][0]
for count in range(t):
	(a, b, n) = input().split()
	a = int(a)
	b = int(b)
	n = int(n)
	print((a * fib(n - 1) + b * fib(n)) % 1000000007)


m = {0: 0, 1: 1}
p = 10 ** 9 + 7

def f(n):
	if n in m:
		return m[n]
	k = (n + 1) // 2
	if n % 2 == 1:
		m[n] = (f(k) * f(k) + f(k - 1) * f(k - 1)) % p
	else:
		m[n] = (2 * f(k - 1) + f(k)) * f(k) % p
	return m[n]
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	print((a * f(n - 1) + b * f(n)) % p)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


import math
phi = 0.5 * (1 + math.sqrt(5))
psi = 0.5 * (1 - math.sqrt(5))

def matMult(A, B):
	assert len(A[0]) == len(B)
	C = []
	for i in range(len(A)):
		C.append([0] * len(B[0]))
	for i in range(len(A)):
		for j in range(len(B[0])):
			for k in range(len(A[0])):
				C[i][j] += A[i][k] * B[k][j]
	return C

def mult2(F, M):
	x = (F[0][0] * M[0][0] % 1000000007 + F[0][1] * M[1][0] % 1000000007) % 1000000007
	y = (F[0][0] * M[0][1] % 1000000007 + F[0][1] * M[1][1] % 1000000007) % 1000000007
	z = (F[1][0] * M[0][0] % 1000000007 + F[1][1] * M[1][0] % 1000000007) % 1000000007
	w = (F[1][0] * M[0][1] % 1000000007 + F[1][1] * M[1][1] % 1000000007) % 1000000007
	R = [[x, y], [z, w]]
	return R

def scalarMult(A, b):
	C = []
	for i in range(len(A)):
		C.append([0] * len(A[0]))
	for i in range(len(A)):
		for j in range(len(A[0])):
			C[i][j] = A[i][j] * b
	return C

def printMat(A):
	for i in range(len(A)):
		for j in A[i]:
			print(j, ' ', end='')
		print()

def matPower(M, n):
	if n == 1:
		return M
	R = matPower(M, n // 2)
	R = mult2(R, R)
	if n % 2 == 1:
		R = mult2(R, M)
	return R

def fib(n, f0):
	a = [[1, 1], [1, 0]]
	a = matPower(a, n - 1)
	x = matMult(a, f0)
	x = (a[0][0] * f0[0][0] % 1000000007 + a[0][1] * f0[1][0] % 1000000007) % 1000000007
	return x
t = int(input())

def Fib2n(Fn1, Fn):
	return (2 * Fn1 + Fn) * Fn

def Fib2n1(Fn1, Fn):
	return Fn * Fn + Fn1 * Fn1
for i in range(t):
	(a, b, n) = map(int, input().split())
	if n == 0:
		print(a)
	elif n == 1:
		print(b)
	else:
		print(fib(n, [[b], [a]]))


M = 10 ** 9 + 7

def matrix_mult(m1, m2):
	return [(m1[0] * m2[0] + m1[1] * m2[2]) % M, (m1[0] * m2[1] + m1[1] * m2[3]) % M, (m1[2] * m2[0] + m1[3] * m2[2]) % M, (m1[2] * m2[1] + m1[3] * m2[3]) % M]

def matrix_vec(m, v):
	return [(m[0] * v[0] + m[1] * v[1]) % M, (m[2] * v[0] + m[3] * v[1]) % M]

def matrix_pow(m, exp):
	if exp == 0:
		return [1, 0, 0, 1]
	if exp == 1:
		return m
	tmp = matrix_pow(m, exp // 2)
	tmp = matrix_mult(tmp, tmp)
	if exp % 2 == 1:
		tmp = matrix_mult(tmp, m)
	return tmp
T = int(input())
for i in range(T):
	(A, B, N) = map(int, input().split())
	F = [1, 1, 1, 0]
	Fn = matrix_pow(F, N)
	v = matrix_vec(Fn, [B, A])
	print(v[1])


MOD = 10 ** 9 + 7

def nthFibo(n, A, B):
	if n < 0:
		raise 'n cannot be negative'
	if n <= 1:
		return n
	result = [[B, A], [A, B - A]]
	fiboM = [[1, 1], [1, 0]]
	while n > 0:
		if n % 2 == 1:
			multMatrix(result, fiboM)
		multMatrix(fiboM, fiboM)
		n //= 2
	ans = result[1][0]
	return ans % MOD

def multMatrix(m, n):
	a = (m[0][0] * n[0][0] % MOD + m[0][1] * n[1][0] % MOD) % MOD
	b = (m[0][0] * n[0][1] % MOD + m[0][1] * n[1][1] % MOD) % MOD
	c = (m[1][0] * n[0][0] % MOD + m[1][1] * n[0][1] % MOD) % MOD
	d = (m[1][0] * n[0][1] % MOD + m[1][1] * n[1][1] % MOD) % MOD
	m[0][0] = a % MOD
	m[0][1] = b % MOD
	m[1][0] = c % MOD
	m[1][1] = d % MOD
T = int(input())
while T > 0:
	(A, B, N) = list(map(int, input().split()))
	fib = 0
	if N == 1:
		fib = B
	else:
		fib = nthFibo(N, A, B)
	print(fib)
	T -= 1


MOD = 10 ** 9 + 7

def matmulmod(A, B, m):
	result = [[0, 0], [0, 0]]
	result[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % m
	result[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % m
	result[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % m
	result[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % m
	return result

def modpowmat(A, e, m):
	acc = [[1, 0], [0, 1]]
	curpow = A
	while e > 0:
		if e & 1:
			acc = matmulmod(acc, curpow, m)
		curpow = matmulmod(curpow, curpow, m)
		e >>= 1
	return acc
for _ in range(int(input())):
	(A, B, N) = map(int, input().strip().split())
	recurrence = [[1, 1], [1, 0]]
	mat = modpowmat(recurrence, N, MOD)
	ans = (mat[1][0] * B + mat[1][1] * A) % MOD
	print(ans)


MOD = int(10 ** 9 + 7)
FIB = [[1, 1], [1, 0]]

def mat_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_r, B_c))) % MOD for B_c in zip(*B)] for A_r in A]

def mat_exp(A, n):
	M = [[1, 0], [0, 1]]
	if n == 0:
		return M
	elif n == 1:
		return A
	E = mat_exp(A, n // 2)
	E = mat_mult(E, E)
	if n % 2:
		E = mat_mult(E, A)
	return E
for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	E = mat_exp(FIB, N)
	print((E[1][0] * B + E[1][1] * A) % MOD)


modVal = 1000000007

def multMatrix(a, b):
	return [(a[0] * b[0] + a[1] * b[2]) % modVal, (a[0] * b[1] + a[1] * b[3]) % modVal, (a[2] * b[0] + a[3] * b[2]) % modVal, (a[2] * b[1] + a[3] * b[3]) % modVal]
squareMatrices = [[1, 1, 1, 0]]
numCases = int(input())
for i in range(numCases):
	(a, b, n) = (int(x) for x in input().split())
	n -= 1
	curBit = 0
	curMatrix = [1, 0, 0, 1]
	while n:
		if curBit >= len(squareMatrices):
			squareMatrices.append(multMatrix(squareMatrices[-1], squareMatrices[-1]))
		curPow = 1 << curBit
		if n % (curPow * 2):
			curMatrix = multMatrix(curMatrix, squareMatrices[curBit])
			n -= curPow
		curBit += 1
	print((b * curMatrix[0] + a * curMatrix[1]) % modVal)


mod = pow(10, 9) + 7

def bar(a, b):
	return [[sum((i * j for (i, j) in zip(a_row, b_col))) % mod for b_col in zip(*b)] for a_row in a]

def foo(m, n):
	M = [[1, 0], [0, 1]]
	if n == 0:
		return M
	elif n == 1:
		return m
	else:
		p = foo(m, n // 2)
		p = bar(p, p)
		if n % 2 == 1:
			p = bar(p, m)
		return p
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	m = foo([[1, 1], [1, 0]], n)
	print((m[1][0] * b + m[1][1] * a) % mod)


import sys
t = int(input().strip())

def matrix_power(mat, n):
	if n == 0 or n == 1:
		return
	mat2 = [[1 for row in range(2)] for col in range(2)]
	mat2[1][1] = 0
	matrix_power(mat, int(n / 2))
	multiply_matrix_matrix(mat, mat)
	if n % 2 != 0:
		multiply_matrix_matrix(mat, mat2)

def multiply_matrix_matrix(mat, mat2):
	x = mat[0][0] * mat2[0][0] % 1000000007 + mat[0][1] * mat2[1][0] % 1000000007
	y = mat[1][0] * mat2[0][0] % 1000000007 + mat[1][1] * mat2[1][0] % 1000000007
	z = mat[0][0] * mat2[0][1] % 1000000007 + mat[0][1] * mat2[1][1] % 1000000007
	w = mat[1][0] * mat2[0][1] % 1000000007 + mat[1][1] * mat2[1][1] % 1000000007
	mat[0][0] = x
	mat[1][0] = y
	mat[0][1] = z
	mat[1][1] = w

def multiply_matrix_vector(mat, v):
	result = [[1 for row in range(2)] for col in range(1)]
	x = mat[0][0] * v[0][0] + mat[0][1] * v[0][1]
	y = mat[1][0] * v[0][0] + mat[1][1] * v[0][1]
	v[0][0] = x
	v[0][1] = y
for a0 in range(t):
	(f0, f1, n) = input().strip().split()
	mat = [[1 for row in range(2)] for col in range(2)]
	mat[1][1] = 0
	v = [[1 for row in range(2)] for col in range(1)]
	v[0][0] = int(f1)
	v[0][1] = int(f0)
	if int(n) == 1:
		print(f1)
	else:
		matrix_power(mat, int(n) - 1)
		multiply_matrix_vector(mat, v)
		print(v[0][0] % 1000000007)


unity = ((1, 1), (1, 0))

def unity_power_mod(power, modular):
	if power == 1:
		return unity
	half = unity_power_mod(power // 2, modular)
	res = [[half[0][0] * half[0][0] + half[0][1] * half[1][0], half[0][0] * half[0][1] + half[0][1] * half[1][1]], [half[1][0] * half[0][0] + half[1][1] * half[1][0], half[1][0] * half[0][1] + half[1][1] * half[1][1]]]
	if power % 2:
		res = [[res[0][0] * unity[0][0] + res[0][1] * unity[1][0], res[0][0] * unity[0][1] + res[0][1] * unity[1][1]], [res[1][0] * unity[0][0] + res[1][1] * unity[1][0], res[1][0] * unity[0][1] + res[1][1] * unity[1][1]]]
	for i in range(2):
		for j in range(2):
			res[i][j] %= modular
	return res

def fibonacci_mod(f0, f1, n, modular):
	if n == 0:
		return f0 % modular
	if n == 1:
		return f1 % modular
	res = unity_power_mod(n - 1, modular)
	return (f1 * res[0][0] + f0 * res[0][1]) % modular
T = int(input())
for _ in range(T):
	(a, b, n) = map(int, input().strip().split())
	print(fibonacci_mod(a, b, n, 10 ** 9 + 7))


import sys

class Matrix:

	def __init__(self, a, b, c, d):
		self.data = ((a, b), (c, d))

	def __str__(self):
		return '[[%d %d]\n [%d %d]]' % (self.data[0][0], self.data[0][1], self.data[1][0], self.data[1][1])

	def __mul__(self, other):
		return Matrix(self.data[0][0] * other.data[0][0] + self.data[0][1] * other.data[1][0], self.data[0][0] * other.data[0][1] + self.data[0][1] * other.data[1][1], self.data[1][0] * other.data[0][0] + self.data[1][1] * other.data[1][0], self.data[1][0] * other.data[0][1] + self.data[1][1] * other.data[1][1])

	def __add__(self, other):
		return Matrix(self.data[0][0] + other.data[0][0], self.data[0][1] + other.data[0][1], self.data[1][0] + other.data[1][0], self.data[1][1] + other.data[1][1])

	def __mod__(self, modulo):
		return Matrix(self.data[0][0] % modulo, self.data[0][1] % modulo, self.data[1][0] % modulo, self.data[1][1] % modulo)

	def __pow__(self, p, modulo):
		if p < 0:
			return None
		if p == 0:
			return Matrix(1, 0, 0, 1)
		bb = []
		while p:
			bb.append(p % 2)
			p //= 2
		m = Matrix(self.data[0][0], self.data[0][1], self.data[1][0], self.data[1][1])
		m %= modulo
		rval = Matrix(1, 0, 0, 1)
		for (i, b) in enumerate(bb):
			if i > 0:
				m = m * m
				m %= modulo
			if b:
				rval *= m
				rval %= modulo
			print('i=%d b=%d\nm=\n%s\nrval=\n%s' % (i, b, m, rval), file=sys.stderr)
		return rval
modulo = pow(10, 9) + 7
q = Matrix(0, 1, 1, 1)
print('q=\n%s' % q, file=sys.stderr)
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	print('a=%d b=%d n=%d' % (a, b, n), file=sys.stderr)
	m = pow(q, n, modulo)
	print(m, file=sys.stderr)
	v = a * m.data[0][0] + b * m.data[0][1]
	v %= modulo
	print(v)


mod = 1000000007

def mm(x, y):
	return x * y % mod

def ma(x, y):
	return (x + y) % mod

def matpow(m, n):
	ans = [[1, 0], [0, 1]]
	while n > 0:
		if n % 2 == 1:
			ans = [[ma(mm(ans[0][0], m[0][0]), mm(ans[0][1], m[1][0])), ma(mm(ans[0][0], m[0][1]), mm(ans[0][1], m[1][1]))], [ma(mm(ans[1][0], m[0][0]), mm(ans[1][1], m[1][0])), ma(mm(ans[1][0], m[0][1]), mm(ans[1][1], m[1][1]))]]
		m = [[ma(mm(m[0][0], m[0][0]), mm(m[0][1], m[1][0])), ma(mm(m[0][0], m[0][1]), mm(m[0][1], m[1][1]))], [ma(mm(m[1][0], m[0][0]), mm(m[1][1], m[1][0])), ma(mm(m[1][0], m[0][1]), mm(m[1][1], m[1][1]))]]
		n = n // 2
	return ans

def vecmult(m, v):
	return [ma(mm(v[0], m[0][0]), mm(v[1], m[0][1])), ma(mm(v[0], m[1][0]), mm(v[1], m[1][1]))]
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	m = [[0, 1], [1, 1]]
	f = vecmult(matpow(m, n - 1), [a, b])
	print(f[1])


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


def modint(x, mod=int(1000000000.0) + 7):
	return int(x % mod)

def matmultmod(M1, M2):
	zip_M2 = list(zip(*M2))
	R = []
	for M1_line in M1:
		R_line = []
		for M2_row in zip_M2:
			tmp = list(map(lambda a, b: modint(a * b), M1_line, M2_row))
			R_line.append(modint(sum(tmp)))
		R.append(R_line)
	return R

def matpown(M, n):
	if n == 1:
		return M
	R = matpown(M, int(n / 2))
	R = matmultmod(R, R)
	if n % 2 == 1:
		R = matmultmod(R, M)
	return R
T = int(input())
for t in range(T):
	splited = input().split(' ')
	A = int(splited[0])
	B = int(splited[1])
	N = int(splited[2])
	if N == 0:
		print(modint(A))
	elif N == 1:
		print(modint(B))
	else:
		Amatrix = [[1, 1], [1, 0]]
		M = [[modint(B)], [modint(A)]]
		Apown = matpown(Amatrix, N - 1)
		M = matmultmod(Apown, M)
		print(M[0][0])


F0 = [1, 1, 3, 21, 987, 2178309, 209783453, 700290221, 745621702, 330235873, 754854590, 961030536, 124518512, 198180511, 314263529, 787294282, 269256820, 462470690, 139070082, 932065818, 580737058, 545755243, 798765759, 810968381, 635507288, 251205278, 445892347, 804101592, 699722224, 900885101, 912848361]
Fn1 = [0, 1, 2, 13, 610, 1346269, 470273943, 761203726, 615649431, 839169006, 754277743, 658059650, 586214508, 706310066, 506099537, 526860082, 193045466, 291309054, 960270309, 464225376, 216587333, 661389053, 543236045, 806163189, 127429331, 559468297, 410375445, 401520518, 977336158, 380127118, 350132037]
Fp1 = [1, 2, 5, 34, 1597, 3524578, 680057396, 461493940, 361271126, 169404872, 509132326, 619090179, 710733020, 904490577, 820363066, 314154357, 462302286, 753779744, 99340384, 396291187, 797324391, 207144289, 342001797, 617131563, 762936619, 810673575, 856267792, 205622103, 677058375, 281012212, 262980391]
M = 1000000007

def sum(lower, zero, new_digit):
	new_lower = zero * F0[new_digit] + lower * Fn1[new_digit]
	new_zero = zero * Fp1[new_digit] + lower * F0[new_digit]
	return (new_lower % M, new_zero % M)
T = int(input())
for _ in range(T):
	(a, b, n) = map(int, input().strip().split())
	if n == 1:
		print(b)
		continue
	lower = 0
	zero = 1
	for (i, c) in enumerate(bin(n - 1)[:1:-1]):
		if c == '1':
			(lower, zero) = sum(lower, zero, i)
	total = (a * lower + b * zero) % M
	print(total)


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


from copy import deepcopy
MOD = 1000000007

def mult(A, B):
	ni = len(A)
	nj = len(B[0])
	nk = len(B)
	C = [[0 for j in range(nj)] for i in range(ni)]
	for i in range(ni):
		for j in range(nj):
			for k in range(nk):
				C[i][j] = (C[i][j] + A[i][k] * B[k][j] % MOD) % MOD
	return C

def m_pow(M, p):
	res = [[1, 0], [0, 1]]
	while p > 0:
		if p % 2 == 1:
			res = mult(res, M)
		M = mult(M, M)
		p //= 2
	return res
t = int(input())
for _ in range(t):
	(f0, f1, n) = [int(i) for i in input().split()]
	if n == 1:
		print(f1)
		continue
	M = [[1, 1], [1, 0]]
	M = m_pow(M, n - 1)
	M = mult(M, [[f1], [f0]])
	print(M[0][0])


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


import copy

class FibonacciPair:

	def __init__(self, a, b):
		self.a = a
		self.b = b

	def __imul__(self, other):
		tmp = self.a * other.a
		self.a = self.a * other.b + self.b * other.a - tmp
		self.b = self.b * other.b + tmp
		return self

	def __imod__(self, modulo):
		self.a %= modulo
		self.b %= modulo
		return self

	def __pow__(self, expo, modulo=None):
		return binary_power(self, expo, modulo, FibonacciPair(0, 1))

def binary_power(a, b, p=None, unity=1):
	result = unity
	a = copy.copy(a)
	while b:
		if b & 1:
			result *= a
			if p:
				result %= p
		b >>= 1
		if not b:
			break
		a *= a
		if p:
			a %= p
	return result
p = 1000000007
for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	f = pow(FibonacciPair(1, 1), n - 1, p)
	print((f.a * a + f.b * b) % p)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


mod = 10 ** 9 + 7

def mult(a, b):
	res = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			res[i][j] = sum((x * y for (x, y) in zip(a[i], (c[j] for c in b)))) % mod
	return res

def get(n):
	a = [[1, 1], [1, 0]]
	res = [[1, 0], [0, 1]]
	while n:
		if n & 1:
			res = mult(res, a)
		a = mult(a, a)
		n //= 2
	return res

def solve():
	(a, b, n) = (int(x) for x in input().split())
	m = get(n)
	print((b * m[1][0] + a * m[1][1]) % mod)
t = int(input())
while t:
	solve()
	t -= 1


fb = {}

def f(n):
	n = int(n)
	if n in fb:
		return fb[n]
	if n == 0:
		fb[0] = 0
		return 0
	if n == 1:
		fb[1] = 1
		return 1
	if n == 2:
		fb[2] = 1
		return 1
	if n % 2:
		fk = f((n - 1) / 2)
		fkx = f((n - 1) / 2 - 1)
		fky = fk + fkx
		fb[(n - 1) // 2 + 1] = fky
		fb[n] = int(fk ** 2 + fky ** 2) % int(1000000000.0 + 7)
		return fb[n]
	fk = f(n / 2)
	fkx = f(n / 2 - 1)
	fky = fk + fkx
	fb[n // 2 + 1] = fky
	fb[n] = int(fk * fkx + fk * fky) % int(1000000000.0 + 7)
	return fb[n]
N = int(input())
for i in range(0, N):
	x = input().split()
	(a, b, c) = (int(x[0]), int(x[1]), int(x[2]))
	print((f(c) * b + f(c - 1) * a) % int(1000000000.0 + 7))


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


def mul(a, b):
	c = [[0] * 2 for i in range(2)]
	for i in range(2):
		for j in range(2):
			for k in range(2):
				c[i][j] += a[i][k] * b[k][j] % (10 ** 9 + 7)
				c[i][j] = c[i][j] % (10 ** 9 + 7)
	return c

def fibb(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	a = [[0] * 2 for i in range(2)]
	a[0][0] = 1
	a[1][0] = 1
	a[0][1] = 1
	a[1][1] = 0
	b = [x[:] for x in a]
	x = 1
	c = [[0] * 2 for i in range(2)]
	while x < n - 1:
		c = b
		b = mul(b, b)
		x = 2 * x
	if x == n - 1:
		return b
	else:
		b = mul(c, fibb(n - int(x / 2)))
	return b

def fibbb(p, q, n):
	b = [[0] * 2 for i in range(2)]
	b[0][0] = p + q
	b[0][1] = q
	b[1][0] = q
	b[1][1] = p
	if n == 2:
		return b
	else:
		return mul(b, fibb(n - 1))
t = int(input())
for j in range(t):
	(a, b, n) = list(map(int, input().split()))
	if n == 0:
		print(a)
	elif n == 1:
		print(b)
	else:
		c = fibbb(a, b, n)
		print(c[0][0])


m = 1000000007

def matrixMultiplication(a, b):
	return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]], [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]]

def matrixAndVectorMultiplication(a, b):
	return [a[0][0] * b[0] + a[0][1] * b[1], a[1][0] * b[0] + a[1][1] * b[1]]

def matrixReduceModulo(a, m):
	return [[a[0][0] % m, a[0][1] % m], [a[1][0] % m, a[1][1] % m]]

def computePowersOfFibonacciMatrix(n, fibonacciMatrix):
	if n in fibonacciMatrix:
		return fibonacciMatrix[n]
	k = n // 2
	fib = computePowersOfFibonacciMatrix(k, fibonacciMatrix)
	fib = matrixMultiplication(fib, fib)
	if n % 2 == 1:
		fib = matrixMultiplication(fib, fibonacciMatrix[1])
	fib = matrixReduceModulo(fib, m)
	fibonacciMatrix[n] = fib
	return fib
T = int(input())
for i in range(T):
	(a, b, n) = map(int, input().split())
	if n == 0:
		print(a)
		continue
	if n == 1:
		print(b)
		continue
	fibonacciMatrix = dict()
	fibonacciMatrix[1] = [[1, 1], [1, 0]]
	computePowersOfFibonacciMatrix(n - 1, fibonacciMatrix)
	vect = matrixAndVectorMultiplication(fibonacciMatrix[n - 1], [b, a])
	ret = vect[0]
	print(ret % m)


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


M = 10 ** 9 + 7

def mul_matrix(a, b):
	return [[(a[i][0] * b[0][j] + a[i][1] * b[1][j]) % M for j in range(2)] for i in range(2)]

def pow_matrix(m, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	q = pow_matrix(m, n // 2)
	q = mul_matrix(q, q)
	if n % 2:
		q = mul_matrix(q, m)
	return q
for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	q = pow_matrix([[1, 1], [1, 0]], N - 1)
	print((B * q[0][0] + A * q[0][1]) % M)


MOD = 10 ** 9 + 7

def mult(a, b):
	return [[(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD, (a[0][0] * b[1][0] + a[0][1] * b[1][1]) % MOD], [(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD, (a[1][0] * b[1][0] + a[1][1] * b[1][1]) % MOD]]
cache = {}

def fib_matrix(exp):
	if exp == 1:
		return [[1, 1], [1, 0]]
	k = 1
	mat_k = [[1, 1], [1, 0]]
	a = [[1, 0], [0, 1]]
	while exp:
		if exp & k:
			a = mult(a, mat_k)
			exp -= k
		if not exp:
			break
		k *= 2
		if k in cache:
			mat_k = cache[k]
		else:
			mat_k = mult(mat_k, mat_k)
			cache[k] = mat_k
	return a

def fib(a, b, c):
	if c == 0:
		return a
	elif c == 1:
		return b
	else:
		m = fib_matrix(c - 1)
		v = m[0]
		return v[0] * b + v[1] * a
for i in range(int(input())):
	print(fib(*map(int, input().split())) % MOD)


import sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, N) = list(map(int, sys.stdin.readline().split()))
	M = matrix_exp(FIB_MATRIX, N)
	print((M[1][0] * B + M[1][1] * A) % MOD)


def multiply(a, b):
	m = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % 1000000007
	n = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % 1000000007
	o = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % 1000000007
	p = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % 1000000007
	a[0][0] = m
	a[0][1] = n
	a[1][0] = o
	a[1][1] = p

def power(mat, n):
	if n == 0 or n == 1:
		return
	t = [[0 for i in range(2)] for j in range(2)]
	t[0][0] = 1
	t[0][1] = 1
	t[1][0] = 1
	t[1][1] = 0
	power(mat, int(n / 2))
	multiply(mat, mat)
	if n % 2 != 0:
		multiply(mat, t)

def fib(a, b, n):
	mat = [[0 for i in range(2)] for j in range(2)]
	mat[0][0] = 1
	mat[0][1] = 1
	mat[1][0] = 1
	mat[1][1] = 0
	power(mat, n)
	return (mat[0][1] * b + mat[1][1] * a) % 1000000007
t = int(input().strip())
for i in range(0, t):
	arr = input().split(' ')
	a = int(arr[0])
	b = int(arr[1])
	n = int(arr[2])
	print(fib(a, b, n))


import sys
t = int(sys.stdin.readline())
m = 10 ** 9 + 7
A = [[1, 1], [1, 0]]

def listmod(A, m):
	for row in A:
		for j in range(len(row)):
			row[j] %= m

def matmul(a, b, res):
	M = len(a)
	N = len(b[0])
	P = len(a[0])
	for i in range(M):
		for j in range(N):
			res[i][j] = sum([a[i][k] * b[k][j] for k in range(P)])
	return res

def powmod(A, x, m, premult):
	result = [[1, 0], [0, 1]]
	next = [[0, 0], [0, 0]]
	i = 0
	while x != 0:
		if x % 2 == 1:
			next = [[0, 0], [0, 0]]
			matmul(result, premult[i], next)
			listmod(next, m)
			result = next
		i += 1
		x = x // 2
	return result
premult = list()
id = [[1, 0], [0, 1]]
last = A
pow = 1
while pow < 10 ** 9:
	premult.append(last)
	next = [[0, 0], [0, 0]]
	matmul(last, last, next)
	last = next
	listmod(last, m)
	pow = pow * 2
for i in range(t):
	(a, b, n) = map(int, sys.stdin.readline().split())
	An = powmod(A, n - 1, m, premult)
	z = matmul(An, [[b], [a]], last)
	print(z[0][0] % m)


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


class MatrixFibonacci:
	Q = [[1, 1], [1, 0]]
	modulo = 1000000007

	def __init__(self):
		self.__memo = {}

	def __multiply_matrix(self, M1, M2):
		R00 = (M1[0][0] * M2[0][0] + M1[0][1] * M2[1][0]) % MatrixFibonacci.modulo
		R01 = (M1[0][0] * M2[0][1] + M1[0][1] * M2[1][1]) % MatrixFibonacci.modulo
		R10 = (M1[1][0] * M2[0][0] + M1[1][1] * M2[1][0]) % MatrixFibonacci.modulo
		R11 = (M1[1][0] * M2[0][1] + M1[1][1] * M2[1][1]) % MatrixFibonacci.modulo
		R = [[R00, R01], [R10, R11]]
		return R

	def __get_matrix_power(self, M, p):
		if p == 1:
			return M
		if p in self.__memo:
			return self.__memo[p]
		K = self.__get_matrix_power(M, int(p / 2))
		R = self.__multiply_matrix(K, K)
		self.__memo[p] = R
		return R

	def get_number(self, n):
		if n == 0:
			return 0
		if n == 1:
			return [0, 1]
		powers = []
		p = 0
		for digit in reversed(bin(n - 1)[2:]):
			if digit == '1':
				powers.append(int(pow(2, p)))
			p += 1
		matrices = [self.__get_matrix_power(MatrixFibonacci.Q, p) for p in powers]
		while len(matrices) > 1:
			M1 = matrices.pop()
			M2 = matrices.pop()
			R = self.__multiply_matrix(M1, M2)
			matrices.append(R)
		return matrices[0][0]

def calculate():
	A = []
	B = []
	N = []
	data_input = []
	modulo = 1000000007
	T = int(input())
	for i in range(T):
		(AA, BB, NN) = [int(x) for x in input().split()]
		data_input += [AA, BB, NN]
	for i in range(T):
		B = int(data_input[1 + 3 * i])
		N = int(data_input[2 + 3 * i])
		if N == 1:
			print(B)
		else:
			A = int(data_input[0 + 3 * i])
			num = MatrixFibonacci().get_number(N)
			print((A * num[1] + B * num[0]) % modulo)
calculate()


mat_mult = 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_mult(A, A) if n == 2 else mat_mult(mat_pow(mat_pow(A, n // 2), 2), A) if n % 2 else mat_pow(mat_pow(A, n // 2), 2)
print('\n'.join(map(lambda a, b, n: str(mat_mult(mat_pow([[0, 1], [1, 1]], n), [[a], [b]])[0][0]), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


maxValue = 1000000007

def mult(x, y):
	return [[(x[0][0] * y[0][0] + x[0][1] * y[1][0]) % maxValue, (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % maxValue], [(x[1][0] * y[0][0] + x[1][1] * y[1][0]) % maxValue, (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % maxValue]]

def fib(x, y, pos):
	if pos == 1:
		return y
	if pos == 0:
		return x
	mat = [[1, 1], [1, 0]]
	n = pos - 1
	e = [[1, 0], [0, 1]]
	while n != 0:
		if n % 2 == 1:
			e = mult(mat, e)
		mat = mult(mat, mat)
		n = n // 2
	return e[0][0] * y + e[0][1] * x
n = int(input().strip())
for i in range(n):
	(x, y, pos) = map(int, input().strip().split(' '))
	print(fib(x, y, pos) % maxValue)


import time
MOD = 10 ** 9 + 7

def matmult(a, b):
	zip_b = zip(*b)
	zip_b = list(zip_b)
	return [[sum((ele_a * ele_b % MOD for (ele_a, ele_b) in zip(row_a, col_b))) for col_b in zip_b] for row_a in a]
assert matmult([[3, 2, 5], [9, 1, 4]], [[1, 2], [3, 4], [5, 6]]) == [[34, 44], [32, 46]]

def expBySquaringMatrices(x, n):
	if n == 0:
		return [[0, 1], [0, 1]]
	elif n == 1:
		return x
	elif n % 2 == 0:
		return expBySquaringMatrices(matmult(x, x), n / 2)
	elif n % 2 == 1:
		return matmult(x, expBySquaringMatrices(matmult(x, x), (n - 1) / 2))
assert expBySquaringMatrices([[0, 1], [1, 1]], 2) == [[1, 1], [1, 2]]

def fib(x1, x2, n):
	return matmult(expBySquaringMatrices([[0, 1], [1, 1]], n), [[x1], [x2]])[0][0]
cases = int(input())
results = []
for a in range(cases):
	(x1, x2, num) = input().split()
	tot = fib(int(x1), int(x2), int(num)) % MOD
	results.append(str(tot))
for ans in results:
	print(ans)


import time
MOD = 1000000007

def matmult(a, b):
	zip_b = zip(*b)
	zip_b = list(zip_b)
	return [[sum((ele_a * ele_b % MOD for (ele_a, ele_b) in zip(row_a, col_b))) for col_b in zip_b] for row_a in a]
assert matmult([[3, 2, 5], [9, 1, 4]], [[1, 2], [3, 4], [5, 6]]) == [[34, 44], [32, 46]]

def expBySquaringMatrices(x, n):
	if n == 0:
		return [[0, 1], [0, 1]]
	elif n == 1:
		return x
	elif n % 2 == 0:
		return expBySquaringMatrices(matmult(x, x), n / 2)
	elif n % 2 == 1:
		return matmult(x, expBySquaringMatrices(matmult(x, x), (n - 1) / 2))
assert expBySquaringMatrices([[0, 1], [1, 1]], 2) == [[1, 1], [1, 2]]

def fib(a, b, n):
	return matmult(expBySquaringMatrices([[0, 1], [1, 1]], n), [[a], [b]])[0][0]
cases = int(input())
results = []
for case in range(cases):
	(a, b, n) = input().split()
	tot = fib(int(a), int(b), int(n)) % MOD
	print(tot)


def mm(x, y):
	try:
		return [[(x[0][0] * y[0][0] + x[0][1] * y[1][0]) % (10 ** 9 + 7), (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % (10 ** 9 + 7)], [(x[1][0] * y[0][0] + x[1][1] * y[1][0]) % (10 ** 9 + 7), (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % (10 ** 9 + 7)]]
	except:
		return [(x[0][0] * y[0] + x[0][1] * y[1]) % (10 ** 9 + 7), (x[1][0] * y[0] + x[1][1] * y[1]) % (10 ** 9 + 7)]
t = int(input())
for test in range(t):
	(f0, f1, n) = list(map(int, input().split()))
	if n == 1:
		print(f1)
	else:
		m = [[1, 0], [0, 1]]
		mp = [[1, 1], [1, 0]]
		while n > 1:
			if n % 2:
				m = mm(m, mp)
				mp = mm(mp, mp)
				n = (n - 1) / 2
			else:
				mp = mm(mp, mp)
				n = n / 2
		print(mm(mm(m, mp), [f1, f0])[int(n)])