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 ≤ 10¹⁵

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

---

hide comments

	David: 2022-01-26 02:33:49 First Java solution! -> Congratulations! Last edit: 2022-08-19 22:27:53
	beet_aizu: 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