There is a rectangular board, we want to build a toy by piling some unit blocks onto it. The toy can be described by the following “height matrix”, which means we need 4 unit blocks in the middle, and 1 unit block at other positions. 111 141 111 We have an unlimited supply of 1 × 1 and 1 × 2 blocks, so we can build the toys in various ways. For example (letters are unit blocks, unit blocks with same letter belongs to the same 1 × 2 block): If at least one 1 × 1 blocks is used we say it’s a silver toy, otherwise we say it’s a gold toy. Given the height matrix, find out the number of silver toys and gold toys we can build. Input There will be at most 20 test cases. Each test case begins with two positive integers R, C (1 ≤ R ∗ C ≤ 16), the number of rows and columns. Each of the following R lines contains C integers h(i, j). (0 ≤ h(i,j) ≤ 20). Output For each test case, print the case number, the number of silver toys and the number of gold toys, both modulo 109 + 7. Sample Input 33 111 141 111 15 11111 22 23 45
2/2 Sample Output Case 1: 485 2 Case 2: 8 0 Case 3: 2794 12