Problem Description

Given an $n \times m$ grid graph with $n$ rows and $m$ columns, there are $n \times m$ vertices in total. There is an edge between every pair of adjacent vertices.

The figure above shows an example of a $3 \times 4$ grid graph.

If some vertices and all edges adjacent to them are deleted from the graph (for example, deleting the vertex at row $2$, column $3$ and the vertex at row $3$, column $1$ in the figure above), the graph becomes as shown below.

A spanning tree of a graph is a subgraph that contains all vertices of the graph and some of its edges, such that for any two vertices there is exactly one unique path made of edges between them. If two spanning trees differ in at least one edge, they are considered different. In the graph above, there are $31$ different spanning trees in total: there are $10$ spanning trees that do not choose edge a, and $21$ spanning trees that choose edge a.

Given the information of which vertices are kept in the grid graph, compute how many different spanning trees the graph has.

Input Format

The first line contains two integers $n$ and $m$, separated by spaces, representing the number of rows and columns of the grid graph.

The next $n$ lines each contain $m$ letters (with no separators). Each letter is either uppercase E or uppercase N. E means the corresponding vertex exists, and N means the corresponding vertex does not exist. It is guaranteed that at least one vertex exists.

Output Format

Output one line containing an integer, the number of spanning trees. The answer may be very large; you only need to output the result modulo $1000000007$ (i.e. $10^9+7$).

3 4
EEEE
EENE
NEEE

31

Hint

For $10\%$ of the testdata, $1 \le n \le 2$.

For $30\%$ of the testdata, $1 \le n \le 3$.

For $40\%$ of the testdata, $1 \le n \le 4$.

For $50\%$ of the testdata, $1 \le n \le 5$.

For another $20\%$ of the testdata, $1 \le n \times m \le 12$.

For another $10\%$ of the testdata, $1 \le m \le 15$.

For $100\%$ of the testdata, $1 \le n \le 6$ and $1 \le m \le 10^5$.

Translated by ChatGPT 5