Yet another counting problem
Time Limit: 1000ms
Memory Limit: 65536kb
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:
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.
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”.
For each test case, output “Case x: ” first, where x is the test case number. Then output the answer mod 1,000,000,007.
1 4 2 3 2 3 4 4 3 4 4 4 0 0 0
Case 1: 10 Case 2: 576 Case 3: 8484138 Case 4: 703632757
The 10 possible game boards in case 1 are: AABA, AABB, ABAA, ABAB, ABBA, BAAB, BABA, BABB, BBAA, BBAB.