题目描述

縦 $H$ マス、横 $W$ マスのグリッドがあります。 上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、$S_{ij}$ が # のとき壁であり、. のとき道です。

マス $(1,1)$ にチェスのクイーンの駒が置いてあります。 クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに $1$ 手で移動することができます。

クイーンの駒がマス $(1,1)$ からマス $(H,W)$ まで移動する方法は何通りありますか？ $\bmod\ (10^9+7)$ で求めてください。

ただし、移動する方法が異なるとは、ある $i$ が存在して、$i$ 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $S_{11}\ldots\ S_{1W}$ $\vdots$ $S_{H1}\ldots\ S_{HW}$

输出格式

クイーンの駒がマス $(1,1)$ から $(H,W)$ まで移動する方法の数を $\mod\ (10^9+7)$ で出力せよ。

题目大意

给一个$H\times W$的图，可以向下，右，右下方移动。其中$.$表示可以通过，#表示不可以通过。求$\left(\ 1,1\right)$到$\left(\ H,W\right)$有多少种方案，总方案要取模$10^9+7$。

3 3
...
.#.
...

10

4 4
...#
....
..#.
....

84

8 10
..........
..........
..........
..........
..........
..........
..........
..........

13701937

提示

制約

• $2\ \leq\ H,W\ \leq\ 2000$
• $S_{ij}$ は # か .
• $S_{11}$ と $S_{HW}$ は .

Sample Explanation 1

移動方法として次の $10$ 通りが考えられます。 - $(1,1)\to\ (1,2)\to\ (1,3)\to\ (2,3)\to\ (3,3)$ - $(1,1)\to\ (1,2)\to\ (1,3)\to\ (3,3)$ - $(1,1)\to\ (1,2)\to\ (2,3)\to\ (3,3)$ - $(1,1)\to\ (1,3)\to\ (2,3)\to\ (3,3)$ - $(1,1)\to\ (1,3)\to\ (3,3)$ - $(1,1)\to\ (2,1)\to\ (3,1)\to\ (3,2)\to\ (3,3)$ - $(1,1)\to\ (2,1)\to\ (3,1)\to\ (3,3)$ - $(1,1)\to\ (2,1)\to\ (3,2)\to\ (3,3)$ - $(1,1)\to\ (3,1)\to\ (3,2)\to\ (3,3)$ - $(1,1)\to\ (3,1)\to\ (3,3)$

Sample Explanation 2

$(1,1)$ からは $1$ 手で $(1,2),(1,3),(2,1),(2,2),(3,1),(4,1)$ のいずれかへ移動することが出来ます。 $(4,4)$ への移動経路として、例えば $(1,1)\to\ (3,1)\to\ (3,2)\to\ (4,3)\to\ (4,4)$ などがあります。

Sample Explanation 3

移動方法の数を $\bmod\ (10^9+7)$ で求めてください。