Counting Unique Spanning Trees in a House

You are given a house represented as an n × m grid. Each cell is either a room or a pillar. A room is represented by the character . and a pillar by #. Initially, every pair of adjacent cells (sharing an edge) is separated by a wall. You want to remove some of these walls between adjacent rooms in order to make all the rooms reachable from one another. However, you have three restrictions:

1. You cannot break through the exterior walls of the house.
2. You cannot remove a wall adjacent to a pillar (in other words, you cannot break a pillar or any wall directly touching a pillar).
3. After removing walls, between any two rooms there should be exactly one unique path (i.e. the network of rooms must form a spanning tree).

In other words, consider a graph whose vertices are the room cells, and an edge exists between two vertices if the corresponding cells are adjacent and their shared wall does not touch any pillar—which is automatically satisfied if both cells are rooms. Count the number of ways to choose a subset of the allowed walls to remove so that the resulting graph is a spanning tree over all rooms. Since the answer can be huge, output it modulo \(10^9\).

Note: The removal operation is only allowed between two adjacent room cells. Walls on the boundary of the house (the exterior walls) are not removed. The condition of a unique path implies that the graph of rooms must be a tree spanning all room cells.

Hint: Use Kirchhoff's Matrix Tree Theorem. Build the Laplacian of the graph, remove any one row and the corresponding column, and then compute the determinant of the resulting matrix. Since the modulo \(10^9\) is composite, you may need to compute the determinant using an exact algorithm such as the Bareiss algorithm.

inputFormat

The first line contains two integers n and m — the number of rows and columns of the grid.

Each of the next n lines contains a string of length m consisting of characters . (room) and # (pillar).

outputFormat

Output a single integer, the number of valid ways to remove walls so that every room is connected via a unique path, modulo \(10^9\).

sample

2 2
..
..

4