Dungeon Creation

Time Limit : 3 sec, Memory Limit : 131072 KB

Dungeon Creation

The king demon is waiting in his dungeon to defeat a brave man. His dungeon consists of H \times W grids. Each cell is connected to four (i.e. north, south, east and west) neighboring cells and some cells are occupied by obstacles.

To attack the brave man, the king demon created and sent a servant that walks around in the dungeon. However, soon the king demon found that the servant does not work as he wants. The servant is too dumb. If the dungeon had cyclic path, it might keep walking along the cycle forever.

In order to make sure that the servant eventually find the brave man, the king demon decided to eliminate all cycles by building walls between cells. At the same time, he must be careful so that there is at least one path between any two cells not occupied by obstacles.

Your task is to write a program that computes in how many ways the kind demon can build walls.


The first line of each test case has two integers H and W (1 \leq H \leq 500, 1 \leq W \leq 15), which are the height and the width of the dungeon. Following H lines consist of exactly W letters each of which is '.' (there is no obstacle on the cell) or '#' (there is an obstacle). You may assume that there is at least one cell that does not have an obstacle.

The input terminates when H = 0 and W = 0. Your program must not output for this case.


For each test case, print its case number and the number of ways that walls can be built in one line. Since the answer can be very big, output in modulo 1,000,000,007.

Sample Input

2 2
3 3
0 0

Output for the Sample Input

Case 1: 4
Case 2: 56

Source: ACM-ICPC Japan Alumni Group Spring Contest 2012 , Tokyo, Japan, 2012-04-15