Problem Description

The board is a rectangle of unit cells with N rows and M columns. At first, cells are all white.For each step, ?? can switch the color of w*h rectangles in the board and at lest one of w and h is equal to 1.White color switches to black color; black color switches to white color. ?? wants to know how many different boards can get within K steps. Two boards are same if corresponding cells are in same color.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each test case consists of three integers: N, M, K, as described on the description above.

limits
T <= 600
1 <= N <= 4
1 <= M <= 10
0 <= K <= N*M

Output

For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the answer you get for that case, as for the answer may be to large, you should output it modulo 1000000007 (1e9 + 7).

2
2 2 1
2 2 2

Case #1: 9
Case #2: 16

Hint

In first case, we can get 9 different boards.(0 denotes white, 1 denotes black)
00 10 01 00 00 11 10 00 01
00 00 00 10 01 00 10 11 01
In second case, we can get all boards.

Author

FZU