Turn Game

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).

Sample Input

2
2 2 1
2 2 2

Sample Output

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

Source

2016 Multi-University Training Contest 4