Score : $100$ points

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$-th row from the top and the $j$-th column from the left.

For each $i$ and $j$ ($1 \leq i \leq H$, $1 \leq j \leq W$), Square $(i, j)$ is described by a character $a_{i, j}$. If $a_{i, j}$ is ., Square $(i, j)$ is an empty square; if $a_{i, j}$ is #, Square $(i, j)$ is a wall square. It is guaranteed that Squares $(1, 1)$ and $(H, W)$ are empty squares.

Taro will start from Square $(1, 1)$ and reach $(H, W)$ by repeatedly moving right or down to an adjacent empty square.

Find the number of Taro's paths from Square $(1, 1)$ to $(H, W)$. As the answer can be extremely large, find the count modulo $10^9 + 7$.

Constraints

• $H$ and $W$ are integers.
• $2 \leq H, W \leq 1000$
• $a_{i, j}$ is . or #.
• Squares $(1, 1)$ and $(H, W)$ are empty squares.

Input

Input is given from Standard Input in the following format:

$H$ $W$

$a_{1, 1}$$\ldots$$a_{1, W}$

$:$

$a_{H, 1}$$\ldots$$a_{H, W}$

Output

Print the number of Taro's paths from Square $(1, 1)$ to $(H, W)$, modulo $10^9 + 7$.

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

3

There are three paths as follows:

5 2
..
#.
..
.#
..

0

There may be no paths.

5 5
..#..
.....
#...#
.....
..#..

24

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

345263555

Be sure to print the count modulo $10^9 + 7$.