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