Tanzibal has got 7 types of tiles with her and there are infinite supplies of each. The following diagram depicts the shape and color of each tile. Tile #1 Color: Red Tile #5 Color: Brown Tile #2 Color: Grey Tile #6 Color: Pink Tile #3 Color: Blue Tile #7 Color: Black Tile #4 Color: Green All the tiles are different in shape and color. For those who are color blind and/or using a black-white printed version of the above figure, the color of each tile is given below its corresponding figure. Tiles numbered 1-4 are L shaped. Tile 5 has a dimension of 2 × 1. Tile 6 has a dimension of 1 × 2. Tile 7 has a dimension of 1 × 1. Tanzibal has a board of size N × M . She would like to cover the board completely with the tiles at her disposal. The rules of tilings goes like this: • The tiles can’t be rotated. • Some of the cells of the board are broken and she can’t place any tile on top of those cells. • Some of the cells of the board are special. Each special cell is marked with a single color. The color of each special cell will be from the set {Red, Grey, Blue, Green, Brown, Pink & Black} and will be denoted by {R, G, B, N, W, P, L} respectively, for the sake of brevity. Tanzibal has to make sure that those cells are covered by a tile with the same color as that of the cell. Can you help Tanzibal by finding out the number of different ways she can tile the whole board? Two configurations are different if there is at least one cell that is tiled with a different color. Input The first line of input is an integer T (T < 50) that indicates the number of test cases. Each case starts with two integers N (0 < N < 9) and M (0 < M < 20) that represents the dimension of the board. Each of the next N lines will contain M characters each. Broken cells will be represented using ‘#’, empty cells will be represented using ‘.’ and the special cells will be given by one of {R, G, B, N, W, P, L}.
2/2 Output For each case, output the case number followed by the total number of configurations. Since the total number of ways can be very big, output the result modulo 50431. Sample Input 3 33 ... ... ... 14 ..#. 22 .. N. Sample Output Case 1: 369 Case 2: 2 Case 3: 0