Crazy Malvika discovers Crazy Fibonacci function

Malvika was getting bored of the usual Fibonacci problems, so she added a twist. She defined a new function f() with these properties:

• You are given two integers, A and B. f(1) is A and f(2) is B.
• For every integer x ≥ 2, f(x) = f(x-1) + f(x+1).

You are given an integer N. Find f(N). Output the answer modulo $10^9+7$.

The first line contains a single integer T, the number of test cases.

Each test case is one line with three integers A, B, and N, where A is f(1), B is f(2), and N is the query.

For each test case, print one line containing f(N).

• $1 \le T \le 10^5$
• $-10^9 \le A, B \le 10^9$
• $1 \le N \le 10^9$

In the first test case, f(3) = 7, so that is the output.

In the second test case, f(3) = -6, and the answer modulo $10^9+7$ is 1000000001.