FIBPWSUM - Fibonacci Power Sum

The fibonacci series is defined as below:

fib(0) = 0, fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) for n > 1

Given three integers N, C and K, find the summation of the following series:

fib(0*C)^K + fib(1*C)^K + fib(2*C)^K + fib(3*C)^K + … + fib(N*C)^K

Since the answer can be huge, output it modulo 1000000007

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 ≤ T ≤ 100
  • 0 ≤ N ≤ 1015
  • 1 ≤ C, K ≤ 10
  • 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
    
    

    Challenge

    Try the harder version here:

    liouzhou_101 - FIBPSUM2

    Added by:sgtlaugh
    Date:2019-02-28
    Time limit:10s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All
    Resource:Own Problem

    hide comments
    2022-01-26 02:33:49 David
    First Java solution!

    -> Congratulations!

    Last edit: 2022-08-19 22:27:53
    2020-02-09 10:30:21
    There is a testcase with N = 0.

    -> Ooops, there was a small typo in the description. Updated from 1 <= N to 0 <= N. Thanks for reporting it!

    Last edit: 2020-02-16 21:11:34
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.