전력망 배선

이전 담당자가 갑작스럽게 세상을 떠나면서, 당신은 베이더 경에게 직접 데스 스타의 새로운 '수석 설계자'로 임명되었다. 당신의 임무는 데스 스타의 모든 구역에 전력을 공급하는 배선 시스템을 설계하는 것이다. 목숨이 성공 여부에 달려 있음을 잘 알기에, 당신은 매우 꼼꼼하게 모든 올바른 배선 구성을 빠짐없이 나열한 뒤 그중 가장 좋은 것을 고르기로 했다.

데스 스타의 지도는 $m \times n$ 격자로 주어지며, 각 칸은 하나의 구역을 나타낸다. 구역 중 정확히 하나는 발전소이고, 나머지는 모두 주거 구역이거나 창고이다. 수평 또는 수직으로 인접한 두 개의 창고가 아닌 구역 사이에는 연결선을 놓을 수 있다. 올바른 배선 구성이란 다음 두 조건을 모두 만족하는 것이다.

• 모든 주거 구역이 발전소와 직접 또는 간접적으로 연결되어 있고,
• 사용하는 연결선의 수가 최소이다. 즉, 어떤 연결선 하나라도 제거하면 어떤 주거 구역이 발전소로부터 끊어진다.

주어진 지도에 대해 올바른 배선 구성은 몇 가지나 존재하는가?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 $m$과 $n$이 적힌 한 줄로 시작한다 ($1 \le m \le 8$, $1 \le n \le 8$). 이어지는 $m$개의 줄에는 각각 $n$개의 문자가 있어 지도를 나타낸다. 정확히 하나의 문자는 발전소를 뜻하는 P이고, 나머지 문자는 주거 구역을 뜻하는 . 또는 창고를 뜻하는 #이다. 올바른 배선 구성이 적어도 하나 존재함이 보장된다. 입력의 끝은 0 0이 적힌 한 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스에 대해, 올바른 배선 구성의 수를 $1{,}000{,}000{,}000$으로 나눈 나머지를 한 줄에 출력한다.