9669: ABC183 —— E - Queen on Grid
[Creator : ]
Description
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.
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.
Input
Input is given from Standard Input in the following format:
```
$H$ $W$
$S_{11}\ldots S_{1W}$
$\vdots$
$S_{H1}\ldots S_{HW}$
```
```
$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)$.
Constraints
- $2 \leq H,W \leq 2000$
- $S_{ij}$ is `#` or `.`.
- $S_{11}$ and $S_{HW}$ are `.`.
- $S_{ij}$ is `#` or `.`.
- $S_{11}$ and $S_{HW}$ are `.`.
Sample 1 Input
3 3
...
.#.
...
Sample 1 Output
10
There are 1010 ways to travel, as follows:
- (1,1)→(1,2)→(1,3)→(2,3)→(3,3)
- (1,1)→(1,2)→(1,3)→(3,3)
- (1,1)→(1,2)→(2,3)→(3,3)
- (1,1)→(1,3)→(2,3)→(3,3)
- (1,1)→(1,3)→(3,3)
- (1,1)→(2,1)→(3,1)→(3,2)→(3,3)
- (1,1)→(2,1)→(3,1)→(3,3)
- (1,1)→(2,1)→(3,2)→(3,3)
- (1,1)→(3,1)→(3,2)→(3,3)
- (1,1)→(3,1)→(3,3)
Sample 2 Input
4 4
...#
....
..#.
....
Sample 2 Output
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)→(3,1)→(3,2)→(4,3)→(4,4).
Sample 3 Input
8 10
..........
..........
..........
..........
..........
..........
..........
..........
Sample 3 Output
13701937