/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{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 で割った余りを出力することを忘れずに。
Score : 100 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
For each i and j (1 \leq i \leq H, 1 \leq j \leq W), Square (i, j) is described by a character a_{i, j}.
If a_{i, j} is ., Square (i, j) is an empty square; if a_{i, j} is #, Square (i, j) is a wall square.
It is guaranteed that Squares (1, 1) and (H, W) are empty squares.
Taro will start from Square (1, 1) and reach (H, W) by repeatedly moving right or down to an adjacent empty square.
Find the number of Taro's paths from Square (1, 1) to (H, W). As the answer can be extremely large, find the count modulo 10^9 + 7.
Constraints
- H and W are integers.
- 2 \leq H, W \leq 1000
- a_{i, j} is
.or#. - Squares (1, 1) and (H, W) are empty squares.
Input
Input is given from Standard Input in the following format:
H W
a_{1, 1}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}
Output
Print the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.
Sample Input 1
3 4 ...# .#.. ....
Sample Output 1
3
There are three paths as follows:
Sample Input 2
5 2 .. #. .. .# ..
Sample Output 2
0
There may be no paths.
Sample Input 3
5 5 ..#.. ..... #...# ..... ..#..
Sample Output 3
24
Sample Input 4
20 20 .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ....................
Sample Output 4
345263555
Be sure to print the count modulo 10^9 + 7.