问题陈述

有一个 $H$ 行 $W$ 列的网格，。让 $(i, j)$ 表示从上往下第 $i$ 行和从左往右第 $j$ 列的正方形。

对于每一个 $i$ 和 $j$ （ $1 \leq i \leq H$ ， $1 \leq j \leq W$ ），方格 $(i, j)$ 都由一个字符 $a_{i, j}$ 来描述。如果 $a_{i, j}$ 是 .，则正方形 $(i, j)$ 是一个空方格；如果 $a_{i, j}$ 是 #，则正方形 $(i, j)$ 是一个墙方格。可以保证方格 $(1, 1)$ 和 $(H, W)$ 是空方格。

太郎将从方格 $(1, 1)$ 开始，通过向右或向下移动到相邻的空方格来到达 $(H, W)$ 。

求太郎从方格 $(1, 1)$ 到 $(H, W)$ 的路径数。由于答案可能非常大，因此求出 $10^9 + 7$ 的模数。

限制因素

• $H$ 和 $W$ 是整数。
• $2 \leq H, W \leq 1000$
• $a_{i, j}$ 是 . 或 #。
• 方格 $(1, 1)$ 和 $(H, W)$ 为空方格。

输入

输入内容由标准输入法提供，格式如下：

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

输出

打印太郎从方格 $(1, 1)$ 到 $(H, W)$ 的路径数，对 $10^9 + 7$ 取模。

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

3

有以下三条路径

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

0

可能没有路径。

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

24

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

345263555

别忘了对 $10^9 + 7$ 取模。

来源

https://atcoder.jp/contests/dp/tasks/dp_h