## FIBOSUMT - Fibonacci extraction Sum

no tags

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(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]).

### 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 0.30s, it could be hard.
A fast C-code can get AC around 0.01s. (Timing edited 2017-02-11, after compiler changes)
Warning: Here is Cube cluster, you can try the classical edition (clone with Pyramid cluster).
Have fun ;-) aniket_1729: 2015-08-06 11:52:57 could k*n+c >10^18? =(Francky)=> (k*N+c)_max is 10^18 + 2^30, that is very near in proportion to 10^18, it could be higher, but in fact no in the input file. Last edit: 2015-08-06 17:59:49 [Lakshman]: 2014-05-17 16:53:02 @Francky any suggestion why I am getting WA. Thanks. --ans(Francky)--> What is the range of your brute force checker ? --Lakshman-> Actually I have checked form many n = 2000000016 +/-1000 and n <= 1000 and randomly chosen c and k. --ans(Francky)--> Then take a look again at your brute force, because you fail very soon. 2 < c,k,n < 4. Last edit: 2014-05-17 17:55:51 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-04-08 21:59:48 Thank you for tutorial edition :)