問題文

縦 $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$ で割った余りを出力せよ。

入力例 1

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

出力例 1

3

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

入力例 2

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

出力例 2

0

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

入力例 3

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

出力例 3

24

入力例 4

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

出力例 4

345263555

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