FIBOSUM2 - Fibonacci extraction Sum

Some people may found FIBOSUM a too easy problem. We propose here a useful variation.

SigmaFibScale

Fib is the Fibonacci sequence:
For any positive integer i: if i<2 Fib(i) = i, else Fib(i) = Fib(i-1) + Fib(i-2)

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 64-bit container, just output your answer modulo 1000000007.

Example

Input:
1
3 5 2

Output:
254

Explanations

Index-1 Fib sequence : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
We want the 5*1+3 = 8th and 5*2+3 = 13th 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 C-code can get AC under 0.15s.
Warning: Here is Pyramid cluster, you can try the tutorial edition (clone with Cube cluster).
Have fun ;-)

Edit(2017-02-11) : With compiler changes, my fast C code ends in 0.01s, my Python3 ones in 0.31s. New TL is 0.5s.


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

hide comments
2018-05-31 10:21:24
My code is running at 0.75s in FIBOSUMT, but it's giving tle here ... How to optimize it more ?

=(Francky)=> Try to work with polynomials instead of matrix each time it's possible. Matrix are slow things.

Last edit: 2018-06-03 17:15:09
2016-02-10 09:00:25 [Rampage] Blue.Mary
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: 2016-02-10 09:01:57
2015-08-06 21:00:23 Francky
With the migration Pyramid => Cube ; some time_limit_s were not chosen by psetter ; here is a case.
I will rejudge all submissions with 1s as time_limit, as it is now, it's too near from FIBOSUMT.
Thanks for your comprehension.

Edit : Done : my old C code ended in 0.02s, and my Py3.4 ended in 0.69s ; with cube cluster.

Last edit: 2015-08-06 21:06:00
2015-08-06 18:19:26
!!!!

Last edit: 2015-08-06 18:52:30
2014-04-08 22:02:48 (Tjandra Satria Gunawan)(曾毅昆)
Thank you for "relax" time limit :D
--ans(Francky)--> ;-) You know that I like when a problem is Python3 possible. Good job : even with "relax" time, it's not easy.

Last edit: 2014-04-08 22:32:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.