FIBPSUM2 - Fibonacci Power Sum (hard)

no tags 

This problem is a harder version of FIBPWSUM.

The Fibonacci numbers is defined by

f0=0,f1=1, f_0=0, f_1=1,

and

fn=fn1+fn2 f_n = f_{n-1}+f_{n-2}

for n>1n > 1

Given three integers NN, CC and KK, compute the summation

n=0NfCnK. \sum_{n=0}^N f_{Cn}^K.

Since the answer can be huge, output it modulo 109+710^9+7.

Input

The first line contains an integer TT, denoting the number of test cases. Each test case contains three space separated integers in the order: NN, CC and KK.

Constraints

  • 1T1001 \leq T \leq 100
  • 1N,C10181 \leq N, C \leq 10^{18}
  • 1K1051 \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
Francky: 2020-06-13 23:40:07

@Speed Addicts : remember that challenge section can offer you stuff like : https://www.spoj.com/problems/PWSUMF/
I'll try to remember how I solved it... or find a new way... Thanks for this new Fib problem...

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