分数: 100 点
问题陈述
有一个网格 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} is .,方形 (i, j) 是一个空方块;如果 a_{i, j} is #,方形 (i, j) 是一个墙方块。
保证正方形 (1, 1) 和 (H, W) 是空方块。
太郎将从广场开始 (1, 1) 并达到 (H, W) 通过重复向右或向下移动到相邻的空方块。
从 Square 中找出太郎的路径数 (1, 1) to (H, W)。 由于答案可能非常大,因此求模数 10^9 + 7.
约束
- H 和 W 是整数。
- 2 \leq H, W \leq 1000
- a_{i, j} is
.or#. - 正方形 (1, 1) 和 (H, W) 是空方块。
输入
输入由标准输入按以下格式给出:
H W
a_{1, 1}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}
输出
打印 Square 中 Taro 的路径数 (1, 1) to (H, W),模数 10^9 + 7.
示例输入 1
3 4 ...# .#.. ....
示例输出 1
3
共有以下三个路径:

示例输入 2
5 2 .. #. .. .# ..
示例输出 2
0
可能没有路径。
示例输入 3
5 5 ..#.. ..... #...# ..... ..#..
示例输出 3
24
示例输入 4
20 20 .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ....................
示例输出 4
345263555
请务必打印模数计数 10^9 + 7.