Crazy Malvika discovers Crazy Fibonacci function
시간 제한1초메모리 제한1024 MB
f(1)=A, f(2)=B이고 f(x) = f(x-1) + f(x+1)인 수열에서 f(N)을 1e9+7로 나눈 나머지를 구한다.
문제
Malvika was getting bored of the usual Fibonacci problems, and decided to add a little twist to it. She defined a new function f() with the following properties:
- She'll give you two integers, A and B. f(1) is defined to be A and f(2) is B.
- And for all integers x ≥ 2, f(x) = f(x-1) + f(x+1).
She'll give an integer N, and you have to find out what f(N) is. Output the answers modulo 109+7.
입력
The first line of input contains a single integer T denoting number of test cases.
The only line of each test case contains three integers: A, B and N, denoting f(1), f(2) and the query.
출력
For each test case, output a line which contains a single integer, corresponding to f(N) for the given input.
제한
- 1 ≤ T ≤ 105
- -109 ≤ A , B ≤ 109
- 1 ≤ N ≤ 109
힌트
In the first test case, f(3) = 7, and so that is the output.
In the second test case, f(3) = -6 and the answer modulo 109+7 is 1000000001.