/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 H マス、横 W マスのグリッドがあります。
上から i 行目、左から j 列目のマス (i,j) は、S_{ij} が # のとき壁であり、. のとき道です。
マス (1,1) にチェスのクイーンの駒が置いてあります。 クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに 1 手で移動することができます。
クイーンの駒がマス (1,1) からマス (H,W) まで移動する方法は何通りありますか？ \bmod (10^9+7) で求めてください。
ただし、移動する方法が異なるとは、ある i が存在して、i 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。
制約
- 2 \leq H,W \leq 2000
- S_{ij} は
#か. - S_{11} と S_{HW} は
.
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}
出力
クイーンの駒がマス (1,1) から (H,W) まで移動する方法の数を \mod (10^9+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 (10^9+7) で求めてください。
Score : 500 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns of squares.
Square (i,j), which is at the i-th row from the top and j-th column from the left, is wall if S_{ij} is # and road if S_{ij} is ..
There is a queen, the chess piece, at Square (1, 1). In one move, it can move any number of squares to the right, downwards, or diagonally to the lower right to a road square without jumping over wall squares.
In how many ways can the queen travel from Square (1, 1) to Square (H, W)? Find the count modulo (10^9+7).
Here, two ways to travel are considered different if and only if there exists i such that the position of the queen after the i-th move is different in those two ways.
Constraints
- 2 \leq H,W \leq 2000
- S_{ij} is
#or.. - S_{11} and S_{HW} are
..
Input
Input is given from Standard Input in the following format:
H W
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}
Output
Print the number of ways, modulo (10^9+7), in which the queen can travel from Square (1, 1) to Square (H, W).
Sample Input 1
3 3 ... .#. ...
Sample Output 1
10
There are 10 ways to travel, as follows:
- (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 Input 2
4 4 ...# .... ..#. ....
Sample Output 2
84
From (1,1), the queen can move to (1,2), (1,3), (2,1), (2,2), (3,1), or (4,1).
One possible path to (4,4) is (1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4).
Sample Input 3
8 10 .......... .......... .......... .......... .......... .......... .......... ..........
Sample Output 3
13701937
Find the count modulo (10^9+7).