FIB2 - Fibonacci number 2
Dữ liệu vào: Standard input
Dữ liệu ra: Standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte

You're given three numbers: A, B, and N, and all you have to do is to find the number FN where:

\(F_0=A,F_1=B, F_i=F_{i-1}+F_{i-2},\forall i\geq2\)

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

Input Format

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

Output Format

For each test case output a single integer \(F_N\) .

Constraints

\(T \leq 10\)
\(1\leq A, B\leq 10, 0<N \leq 10^6\)
 

Ví dụ

  • input
    2
    1 1 3
    2 3 2
    output
    3
    5

 

 
Back to Top