[Login|Register]
Problems

Status

Rank

Problem 1289
Yet another counting problem
Time Limit: 1000ms
Memory Limit: 65536kb
Description

Bejeweled is a popular computer game played with k kinds of jewels. The game board consists of an n × m grid, which is filled with nm jewels. The goal of game is to erase as many jewels as possible by swapping consecutive jewels. When the player swaps any two consecutive jewels, the game:

  1. erases consecutive jewels of the same kind in a single line, if there are 3 or more of such jewels.
  2. moves jewels in each column down to the empty cells.
  3. repeats this process until no more jewels get erased.

The goal of game is to erase as many jewels as possible by swapping consecutive jewels. Player can swap any two consecutive jewels if 3 or more jewels get erased after swapping.

You task is to count the number of different game board in which no jewels get erased, i.e. there’s no 3 consecutive jewels of same kind in a single line.

Input

The input consists of multiple test cases. Each test case contains only three integers n, m and k in a single line, which are explained above. (1 ≤ n,m ≤ 6, 1 ≤ k ≤ 4)

The input ends with “0 0 0”.

Output

For each test case, output “Case x: ” first, where x is the test case number. Then output the answer mod 1,000,000,007.

Sample Input
1 4 2
3 2 3
4 4 3
4 4 4
0 0 0
Sample Output
Case 1: 10
Case 2: 576
Case 3: 8484138
Case 4: 703632757
Hint

The 10 possible game boards in case 1 are: AABA, AABB, ABAA, ABAB, ABBA, BAAB, BABA, BABB, BBAA, BBAB.

University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.7ms with 1 query(s).