Dungeon Creation

A demon king waits in his dungeon to defeat a hero. The dungeon is a grid with $H$ rows and $W$ columns. Each cell is connected to its four neighbours to the north, south, east and west, and some cells hold obstacles.

To attack the hero, the demon king made a servant and sent it walking through the dungeon. The servant turned out to be dumb. If the dungeon has a cyclic path, the servant might walk along that cycle forever.

So that the servant eventually finds the hero, the demon king decided to remove every cycle by building walls between neighbouring cells. A wall can only be built between two neighbouring cells that hold no obstacle, and a wall stops movement between those two cells. At the same time, at least one path must remain between any two cells that hold no obstacle.

Write a program that counts the ways to build walls so that both conditions hold. Two ways are different when the sets of built walls differ.

The input holds several test cases.

The first line of each test case has two integers $H$ and $W$ ($1 \leq H \leq 500$, $1 \leq W \leq 15$), the height and the width of the dungeon. The following $H$ lines hold exactly $W$ characters each. . is a cell with no obstacle and # is a cell with an obstacle. Every test case has at least one cell with no obstacle.

The last line of the input holds 0 0, and that line is not a test case.

For each test case print one line in the form Case x: y, where $x$ is the test case number starting at 1 and $y$ is the number of ways to build the walls, taken modulo 1,000,000,007.

If the obstacles split the cells with no obstacle into two or more parts, no arrangement satisfies the conditions, so print 0. Print nothing for the last line of the input.