#FIBPWSUM. Fibonacci Power Sum

    ID: 3831 远端评测题 10000ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>combinatoricslinear-recurrencematrixexpoberlekamp-massey

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(0C)^K + fib(1C)^K + fib(2C)^K + fib(3C)^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

<li>1 ≤ T ≤ 100</li> <li>0 ≤ N ≤ 1015</li> <li>1 ≤ C, K ≤ 10</li>

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