던전 만들기

마왕은 용사를 물리치려고 자신의 던전에서 기다리고 있다. 던전은 세로 $H$칸, 가로 $W$칸의 격자다. 각 칸은 동서남북으로 인접한 네 칸과 이어져 있고, 일부 칸에는 장애물이 놓여 있다.

마왕은 용사를 공격하려고 던전 안을 돌아다니는 하수인을 만들어 보냈다. 그런데 하수인은 머리가 나빠서, 던전에 순환하는 경로가 있으면 그 길을 따라 영원히 맴돌 수도 있다.

하수인이 언젠가는 용사를 찾아내도록, 마왕은 인접한 두 칸 사이에 벽을 세워 모든 순환 경로를 없애기로 했다. 벽은 장애물이 없는 인접한 두 칸 사이에만 세울 수 있고, 벽이 있으면 그 두 칸은 서로 오갈 수 없다. 동시에 장애물이 없는 어떤 두 칸 사이에도 경로가 적어도 하나는 남아 있어야 한다.

두 조건을 모두 만족하도록 벽을 세우는 방법의 수를 구하는 프로그램을 작성하시오. 세운 벽의 집합이 다르면 서로 다른 방법으로 센다.

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 던전의 세로 길이 $H$와 가로 길이 $W$가 주어진다 ($1 \leq H \leq 500$, $1 \leq W \leq 15$). 이어지는 $H$개 줄에는 각각 정확히 $W$개의 문자가 주어진다. .은 장애물이 없는 칸, #은 장애물이 있는 칸이다. 각 테스트 케이스에는 장애물이 없는 칸이 적어도 하나 있다.

입력의 마지막 줄에는 0 0이 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 벽을 세우는 방법의 수를 1,000,000,007로 나눈 나머지다.

장애물 때문에 장애물이 없는 칸이 둘 이상의 덩어리로 나뉘면 조건을 만족하는 방법이 없으므로 0을 출력한다. 입력의 마지막 줄에 대해서는 아무것도 출력하지 않는다.