問題文
縦 H マス、横 W マスのグリッドがあります。 上から i 行目、左から j 列目のマス (i,j) は、Sij が # のとき壁であり、. のとき道です。
マス (1,1) にチェスのクイーンの駒が置いてあります。 クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに 1 手で移動することができます。
クイーンの駒がマス (1,1) からマス (H,W) まで移動する方法は何通りありますか？ bmod(109+7) で求めてください。
ただし、移動する方法が異なるとは、ある i が存在して、i 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。
制約
- 2leqH,Wleq2000
- Sij は
# か .
- S11 と SHW は
.
入力
入力は以下の形式で標準入力から与えられる。
H W
S11ldotsS1W
vdots
SH1ldotsSHW
出力
クイーンの駒がマス (1,1) から (H,W) まで移動する方法の数を mod(109+7) で出力せよ。
入力例 1
3 3
...
.#.
...
出力例 1
10
移動方法として次の 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)
入力例 2
4 4
...#
....
..#.
....
出力例 2
84
(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) などがあります。
入力例 3
8 10
..........
..........
..........
..........
..........
..........
..........
..........
出力例 3
13701937
移動方法の数を bmod(109+7) で求めてください。
