Crazy Malvika가 Crazy 피보나치 함수를 발견하다
면접 대비시간 제한1초메모리 제한1024 MB
f(1)이 A, f(2)가 B이고 f(x)=f(x-1)+f(x+1)을 따르는 함수에서 f(N)을 10^9+7로 나눈 나머지를 구합니다.
문제
Malvika는 평범한 피보나치 문제에 싫증이 나서 변형을 하나 더했다. 그녀는 다음 성질을 가진 새 함수 f()를 정의했다.
- 정수 A와 B가 주어진다. f(1)은 A이고 f(2)는 B이다.
- 모든 정수 x ≥ 2에 대해 f(x) = f(x-1) + f(x+1)이다.
정수 N이 주어지면 f(N)을 구하라. 답은 로 나눈 나머지를 출력한다.
입력
첫 줄에 테스트 케이스의 개수를 나타내는 정수 T가 주어진다.
각 테스트 케이스는 한 줄이며, 정수 A, B, N이 주어진다. A는 f(1), B는 f(2), N은 질의하는 값이다.
출력
각 테스트 케이스마다 f(N)을 한 줄에 출력한다.
제한
힌트
첫 번째 테스트 케이스에서는 f(3) = 7이므로 이 값이 출력이다.
두 번째 테스트 케이스에서는 f(3) = -6이고, 이를 로 나눈 나머지는 1000000001이다.