Power Grid

After the untimely demise of its previous tenant, you have been promoted to the position of new "chief architect" of the Death Star by Lord Vader himself. You are tasked with designing the wiring system that distributes power throughout every sector of the Death Star. Knowing that your life depends on your success, you have decided to be extremely meticulous and to enumerate every valid wiring configuration so that you can choose the best one.

You are given a map of the Death Star as an $m \times n$ grid whose cells correspond to sectors. Exactly one sector is a power station; every other sector is either a living quarter or a storage unit. You may place a connection between any two non-storage sectors that are horizontally or vertically adjacent. A wiring configuration is valid when both of the following hold:

• Every living-quarter sector is connected, directly or indirectly, to the power-station sector, and
• It uses as few connections as possible — removing any single connection would disconnect some living quarter from the power station.

For a given map, how many valid wiring configurations exist?

The input contains several test cases. Each test case begins with a line containing two integers $m$ and $n$ ($1 \le m \le 8$, $1 \le n \le 8$). The next $m$ lines each contain $n$ characters describing the map. Exactly one character is a power station, written P; each of the remaining characters is either a living quarter, written ., or a storage unit, written #. It is guaranteed that at least one valid wiring configuration exists. The input ends with a line containing 0 0, which must not be processed.

For each test case, print on its own line the number of valid wiring configurations, taken modulo $1{,}000{,}000{,}000$.