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