FIBPSUM2  Fibonacci Power Sum (hard)
This problem is a harder version of FIBPWSUM.
The Fibonacci numbers is defined by
$$ f_0=0, f_1=1, $$
and
$$ f_n = f_{n1}+f_{n2} $$
for $n > 1$.
Given three integers $N$, $C$ and $K$, compute the summation
$$ \sum_{n=0}^N f_{Cn}^K. $$
Since the answer can be huge, output it modulo $10^9+7$.
Input
The first line contains an integer $T$, denoting the number of test cases. Each test case contains three space separated integers in the order: $N$, $C$ and $K$.
Constraints
Output
For each test case, output a single line in the format “Case X: Y” without the quotes. Here, X is the case number and Y is the desired answer denoting the sum of the series.
Example
Input:
5
10 1 1
5 2 2
3 3 4
1000000007 7 9
996969696969696 9 6
Output:
Case 1: 143
Case 2: 3540
Case 3: 1340448
Case 4: 880410497
Case 5: 689328397
Credits
Information
There are two test files. The first file is randomly generated while the second file is not.
@Speed Adicts: My solution runs in 1.94s. (approx less than 1s per file)
hide comments
Francky:
20200613 23:40:07
@Speed Addicts : remember that challenge section can offer you stuff like : https://www.spoj.com/problems/PWSUMF/


Scape:
20190316 20:06:42
Haha, I wanted to create a harder version of this problem with the exact same constraints, but looks like you beat me to it :)

Added by:  liouzhou_101 
Date:  20190304 
Time limit:  20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  FIBPWSUM 