#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Mushroom Land is represented by a grid of *N* by *M* grid squares. Each grid square can be empty, '.', or an obstacle, '#'. A dog and a cat start on the top left corner of Mushroom Land, and wishes to get to the bottom right corner of Mushroom Land. At each step, they are allowed to move down or right, but as they do not like each other, their paths cannot intersect other than at the start and end points, i.e. they cannot be on the same square. Help them figure out how many possible ways both of them can travel this journey, while meeting such a condition, modulo 10^{9} + 7.

## Input

The first line of input will contain two integers, *N* and *M*.

The next *N* lines of input will contain *M* characters each, representing the grid. It is guaranteed that the top left and bottom right corner squares are empty.

## Output

The output should contain one line with one integer, the total number of ways the above scenario could occur, modulo 10^{9} + 7.

## Limits

Subtask 1 (27%): 3 ≤ N, M ≤ 70.

Subtask 2 (33%): 3 ≤ N, M ≤ 300.

Subtask 3 (40%): 3 ≤ N, M ≤ 2000.

Subtask 4 (0%): Sample Testcases.

## Sample Input 1

3 3 ... .#. ...

## Sample Output 1

2

## Explanation for Sample 1

The dog can take the top path from top-left to bottom-right, and the cat can take the bottom path from top-left to bottom-right. The two can swap roles as well.

## Sample Input 2

4 3 ... .#. ... ...

## Sample Output 2

4

## Explanation for Sample 2

The animal that takes the top path has only one path, the bottom animal has two possible paths.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 27 | 22 | 1s | 256MB | Minimum |

2 | 33 | 42 | 1s | 256MB | Minimum |

3 | 40 | 62 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o catdog -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512