Problems Status Rank Problem 1289 Yet another counting problem Time Limit: 1000msMemory 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: erases consecutive jewels of the same kind in a single line, if there are 3 or more of such jewels. moves jewels in each column down to the empty cells. 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.