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:
    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
    Scape: 2019-03-16 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 :)

    I did not know about the existence of the ZOJ problem, thanks for sharing


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