配点 : $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}$ が . ならばマス $(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

経路は次図の $3$ 通りです。

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

0

経路が存在しない場合もあります。

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

24

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

345263555

答えを $10^9 + 7$ で割った余りを出力することを忘れずに。