Counting Spanning Trees in a Grid Graph with Removed Vertices

You are given a grid graph of size \(n \times m\) with \(n\) rows and \(m\) columns, comprising \(n\times m\) vertices. There is an edge between every pair of adjacent vertices (i.e. vertices that share a common side). Some vertices are removed from the grid together with all edges incident to them.

For example, consider a \(3\times 4\) grid. After removing the vertex at row 2, column 3 and the vertex at row 3, column 1, the graph becomes disconnected in some regions. In the remaining connected graph (if it is connected), a spanning tree is defined as a subset of edges that connects all of the remaining vertices, and any two vertices in the connected component have exactly one simple path between them. Two spanning trees are considered different if there is at least one edge which is present in one tree but not in the other.

Your task is to count the total number of different spanning trees in the remaining graph. If the graph is disconnected, output 0.

Note: The number of spanning trees for a connected graph can be computed using Kirchhoff's Matrix Tree Theorem. In this theorem, if \(L\) is the Laplacian matrix of the graph, then any cofactor (i.e. the determinant of \(L\) with any row and corresponding column removed) is equal to the number of spanning trees. All mathematical formulas are presented in \(\LaTeX\) format.

Input Format: The first line contains two integers \(n\) and \(m\) indicating the dimensions of the grid. The following \(n\) lines each contain \(m\) integers (either 0 or 1) separated by spaces. A value of 1 indicates that the vertex is present, and a value of 0 indicates that the vertex is removed.

Output Format: Output a single integer representing the number of spanning trees in the graph induced by the remaining vertices. If the graph is disconnected, output 0.

inputFormat

The first line contains two integers \(n\) and \(m\). \(n\) denotes the number of rows and \(m\) the number of columns. Each of the next \(n\) lines contains \(m\) space-separated integers (either 0 or 1), representing the grid. A 1 means that the vertex is kept; a 0 means that it is removed.

outputFormat

Output a single integer: the number of spanning trees in the graph consisting of the remaining vertices. If the graph is disconnected, output 0.

sample

3 4
1 1 1 1
1 1 0 1
0 1 1 1

31