Description

Xiaoming is very interested in building blocks. All of his blocks are identical upright cubes.

When building, Xiaoming chooses $m$ blocks as the foundation, places them in a straight line on the table with no gaps, and calls this layer $0$.

Then, Xiaoming can place layer $1$, layer $2$, $\ldots$, up to at most layer $n$. Placing blocks must follow three rules:

Rule $1$: Each block must be placed directly above some block, tightly adjacent to it, and aligned with the block in the layer below.

Rule $2$: Blocks in the same layer must be placed continuously, with no gaps in between.

Rule $3$: Blocks cannot be placed in positions that Xiaoming dislikes.

All positions that Xiaoming dislikes are marked on the blueprint. The blueprint has $n$ rows. From bottom to top, each row corresponds to layers $1$ to $n$ of the blocks. Each row has $m$ characters, which are either . or X, where X indicates a position that Xiaoming dislikes.

Now Xiaoming wants to know how many different ways there are to place the blocks. He asks you, as a Lanqiao Cup contestant, to help compute the answer.

Since the answer may be very large, you only need to output the result modulo $1000000007(10^9+7)$.

Note: Placing nothing above the foundation is also considered one valid arrangement.

Input Format

The first line of the input contains two positive integers $n$ and $m$, representing the size of the blueprint.

The next $n$ lines each contain $m$ characters describing the blueprint. Each character is either . or X.

Output Format

Output one integer, the answer modulo $10^9+7$.

2 3
..X
.X.

4

Hint

Sample Explanation

Valid placements are as follows (where O means a block is placed):

 1       2       3       4
..X     ..X     O.X     ..X
.X.     OX.     OX.     .XO

Constraints

For $10\%$ of the testdata, $n=1$, $m \le 30$.

For $40\%$ of the testdata, $n \le 10$, $m \le 30$.

For $100\%$ of the testdata, $n \le 100$, $m \le 100$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2018, 9th National Finals.

Translated by ChatGPT 5