## FIBPSUM2 - Fibonacci Power Sum (hard)

no tags

This problem is a harder version of FIBPWSUM.

The Fibonacci numbers is defined by

$$f_0=0, f_1=1,$$

and

$$f_n = f_{n-1}+f_{n-2}$$

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

• $1 \leq T \leq 100$
• $1 \leq N, C \leq 10^{18}$
• $1 \leq K \leq 10^5$
• ### 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:510 1 15 2 23 3 41000000007 7 9996969696969696 9 6
Output:Case 1: 143Case 2: 3540Case 3: 1340448Case 4: 880410497Case 5: 689328397

### 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)