P4111 [HEOI2015] Xiao Z's Room

You suddenly have a big house, which contains some rooms. In fact, your house can be regarded as a grid rectangle with $n\times m$ cells, where each cell is either a room or a pillar. Initially, there is a wall between every pair of adjacent cells. You want to knock down some walls between adjacent rooms so that all rooms become mutually reachable. During this process, you must not break through the house boundary, nor open a pillar (as well as the walls next to a pillar). Meanwhile, you do not want it to be hard to catch thieves, so you require that there be exactly one path between any two rooms. Now, count how many feasible plans there are; output the answer modulo $10^9$.

The first line contains two integers $n,m$. Then follow $n$ lines, each containing $m$ characters `.` or `*`, where `.` denotes a room and `*` denotes a pillar.

Output a single integer, the number of valid plans modulo $10^9$.

Constraints - For $20\%$ of the testdata, $n,m \le 3$. - For $50\%$ of the testdata, $n,m \le 5$. - For $40\%$ of the testdata, $\min(n,m) \le 3$. - For $30\%$ of the testdata, there are no pillars. - For $100\%$ of the testdata, $1 \le n,m \le 9$. Translated by ChatGPT 5