Grid Walker

Grid Walker

You start at the top-left cell of an r x c grid and want to reach the bottom-right ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​‌​‌‌​​​‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​‌​cell, moving only right or down one cell at a time. Some cells are blocked (#) and cannot be entered; the rest are open (.). The start and end cells are always open. Count the number of distinct paths, ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​‌​‌‌​​​‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​‌​modulo 1,000,000,007.

Input

Line 1: two integers r c (1 ≤ r, c ≤ 1000) Next r lines: a string of c characters, each . or #.

Output

A single integer: the number of paths modulo 1,000,000,007.

Example

​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​‌​‌‌​​​‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​‌​Input:

3 3
...
.#.
...

Output:

2

Constraints

• 1 ≤ r, c ≤ 1000 ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​‌​‌‌​​​‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​‌​

2 2
..
..

2

3 3
...
.#.
...

2