题目描述

有一个由 $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)$ 是空方格。

Taro 从方格 $(1, 1)$ 出发，通过重复向右或向下移动到相邻的空方格，最终到达 $(H, W)$。

找出 Taro 从方格 $(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}$ $\ldots$ $a_{H, 1}\ldots a_{H, W}$

输出

打印 Taro 从方格 $(1, 1)$ 到 $(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$。