Bessie’s Mural

Bessie the artist is working on a mural. The mural is drawn on a grid with (N) rows and (M) columns, where (1 \le N, M \le 1000). Each cell is either a stone (represented by a '#' character) or blank (represented by a '.' character). Stones have been painted in some cells – in fact, all cells on the boundary are stones. Now Bessie may choose to paint some of the blank cells with water. However, the painting must satisfy the following condition:

For any cell (a) that is painted water (initially a blank cell that Bessie fills), if there exists a path from (a) to another cell (b) such that every cell on the path (which moves only between horizontally or vertically adjacent cells) is either blank or water and has height no more than the height of (a), then cell (b) must also be painted water. (The height of a cell in the (i)th row is defined as (N+1-i).)

In other words, if a blank cell in some row is filled with water then every blank cell in the same connected region (when considering only moves that do not go to a cell of higher height, i.e. only moves in the same row or downward) that is reachable from it must also be painted water. Note that water does not flow upward.

A key observation is that, if we consider a maximal connected component (using the usual four‐direction connectivity) of blank cells, then any valid water painting within that component is forced to be "vertical monotonic." That is, if the component spans rows (r) through (s) (so that (s-r+1) is the number of rows in the component), then the only valid ways to paint water in that component are to choose a threshold (t) (with (r \le t \le s+1)) so that every blank cell in a row (\ge t) is painted water and every blank cell in a row (< t) is left blank. (Here, choosing (t=s+1) corresponds to leaving the entire component empty.)

Thus, the number of valid water‐paintings in a connected component is ((s-r+1)+1) (i.e. the number of rows spanned plus one). Since choices in different components are independent, the answer is the product (over every blank component) of (\bigl(#\text{rows in component} + 1\bigr)) modulo (10^9+7).

Your task is to compute the number of valid paintings Bessie can make modulo (10^9+7).

inputFormat

The first line contains two integers (N) and (M). Each of the next (N) lines contains a string of length (M) consisting of characters '#' and '.', representing the mural. It is guaranteed that all boundary cells (i.e. cells in the first and last row, and first and last column) are '#' (stones).

outputFormat

Output a single integer – the number of valid paintings modulo (10^9+7).

sample

2 3
#.#
###

2