SP19406 FIBOSUM2 - Fibonacci extraction Sum
Description
Some people may found [FIBOSUM](http://www.spoj.com/problems/FIBOSUM/) a too easy problem. We propose here a useful variation.
 Fib is the Fibonacci sequence: For any positive integer i: if i
Input Format
The first line of input contains an integer **_T_**, the number of test cases. On each of the next **_T_** lines, your are given tree integers **_c_**, **_k_**, **_N_**.
Output Format
Print **Sum(Fib(_ki+c_) for _i_ in \[1.._N_\])**. As the answer could not fit in a 64-bit container, just output your answer modulo 1000000007.