Description

Xiao Ming is very interested in building blocks. All his blocks are identical cubes of the same size.

When building, Xiao Ming selects m blocks as the foundation, arranges them in a straight line on the table without any gaps, and calls this the 0th layer.

Subsequently, Xiao Ming can place the 1st layer, 2nd layer, ..., up to the nth layer on top. The placement of blocks must follow three rules:

Rule 1: Each block must be placed directly above a block from the layer below, aligned with it.
Rule 2: Blocks in the same layer must be placed consecutively without any gaps.
Rule 3: Blocks cannot be placed in positions that Xiao Ming dislikes.

The disliked positions are marked on a blueprint. The blueprint consists of n rows, corresponding to the 1st to nth layers from bottom to top. Each row has m characters, which can be either '.' or 'X', where 'X' indicates a position that Xiao Ming dislikes.

Now, Xiao Ming wants to know how many possible ways there are to place the blocks. He has asked you, a participant in the Blue Bridge Cup, to help him calculate this answer.

Since the answer may be very large, you only need to provide the result modulo 1,000,000,007 (one billion and seven).

Note: Not placing any blocks on the foundation is also considered one valid solution.

Input Format

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

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

For 10% of the data, n = 1 and m <= 30.
For 40% of the data, n <= 10 and m <= 30.
For 100% of the data, n <= 100 and m <= 100.

Output Format

Output an integer representing the answer modulo 1,000,000,007.

2 3
..X
.X.

4

3 3
..X
.X.
...

16

Hint

Explanation for Sample 1:

Successful placements (where O represents placed blocks):

(1)

..X

.X.

(2)

..X

OX.

(3)

O.X

OX.

(4)

..X

.XO

Source

2018 9th Lanqiao Cup C/C++ Group B National Finals Real Question