eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Dungeon Creation

Dungeon Creation

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

The king demon is waiting in his dungeon to defeat a brave man. His dungeon consists of H×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 (1H500, 1W15), 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 1000000007.

Приклад

Вхідні дані #1
2 2
..
..
3 3
...
...
..#
0 0
Вихідні дані #1
Case 1: 4
Case 2: 56
Джерело ACM-ICPC Japan Alumni Group Spring Contest 2012 , Tokyo, Japan, 2012-04-15