P8675 [Lanqiao Cup 2018 National B] Building Blocks.

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.

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 one integer, the answer modulo $10^9+7$.

**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