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 another block, aligned with the block in the layer below 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.

Xiao Ming's disliked positions are marked on a blueprint. The blueprint consists of n rows, corresponding to the 1st to nth layers of the blocks 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 might be very large, you only need to provide the result modulo 1000000007 (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 following n lines each contain m characters, describing the blueprint. Each character is either '.' or 'X'.

For 10% of the data, n=1, m≤30;

For 40% of the data, n≤10, m≤30;

For 100% of the data, n≤100, m≤100.

Output Format

Output an integer representing the result modulo 1000000007.

```input1 2 3 ..X .X.

```output1
4

3 3
..X
.X.
...

16

Hint

Explanation for Sample Case 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