FIBOSUM2  Fibonacci extraction Sum
Some people may found FIBOSUM a too easy problem. We propose here a useful variation.
Fib is the Fibonacci sequence:
For any positive integer i: if i<2 Fib(i) = i, else Fib(i) = Fib(i1) + Fib(i2)
Input
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
Print Sum(Fib(ki+c) for i in [1..N]).
As the answer could not fit in a 64bit container, just output your answer modulo 1000000007.
Example
Input: 1 3 5 2
Output: 254
Explanations
Index1 Fib sequence : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
We want the 5*1+3 = 8^{th} and 5*2+3 = 13^{th} ones, thus the answer is 21 + 233 = 254.
Constraints
0 < T <= 60606 0 <= c < k <= 2^15 0 < N <= 10^18
The numbers c,k,N are uniform randomly chosen in their range.
For your information, constraints allow 1.3kB of Python3 code to get AC in 6.66s, it could be hard.
A fast Ccode can get AC under 0.15s.
Warning: Here is Pyramid cluster, you can try the tutorial edition (clone with Cube cluster).
Have fun ;)
Edit(20170211) : With compiler changes, my fast C code ends in 0.01s, my Python3 ones in 0.31s. New TL is 0.5s.
hide comments
aviroop123:
20180531 10:21:24
My code is running at 0.75s in FIBOSUMT, but it's giving tle here ... How to optimize it more ?


[Rampage] Blue.Mary:
20160210 09:00:25
I know there's some mathematical way to solve this problem which I don't know now; however, I have to use heavy constant optimization to pass the time limit with my strategy(with little math knowledge). Last edit: 20160210 09:01:57 

Francky:
20150806 21:00:23
With the migration Pyramid => Cube ; some time_limit_s were not chosen by psetter ; here is a case.


aniket_1729:
20150806 18:19:26
!!!! Last edit: 20150806 18:52:30 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140408 22:02:48
Thank you for "relax" time limit :D

Added by:  Francky 
Date:  20140405 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 