{"raw_statement":[{"iden":"problem statement","content":"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 `.`.\nThere 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.\nIn how many ways can the queen travel from Square $(1, 1)$ to Square $(H, W)$? Find the count modulo $(10^9+7)$.\nHere, 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."},{"iden":"constraints","content":"*   $2 \\leq H,W \\leq 2000$\n*   $S_{ij}$ is `#` or `.`.\n*   $S_{11}$ and $S_{HW}$ are `.`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$\n$S_{11}\\ldots S_{1W}$\n$\\vdots$\n$S_{H1}\\ldots S_{HW}$"},{"iden":"sample input 1","content":"3 3\n...\n.#.\n..."},{"iden":"sample output 1","content":"10\n\nThere are $10$ ways to travel, as follows:\n\n*   $(1,1)\\to (1,2)\\to (1,3)\\to (2,3)\\to (3,3)$\n*   $(1,1)\\to (1,2)\\to (1,3)\\to (3,3)$\n*   $(1,1)\\to (1,2)\\to (2,3)\\to (3,3)$\n*   $(1,1)\\to (1,3)\\to (2,3)\\to (3,3)$\n*   $(1,1)\\to (1,3)\\to (3,3)$\n*   $(1,1)\\to (2,1)\\to (3,1)\\to (3,2)\\to (3,3)$\n*   $(1,1)\\to (2,1)\\to (3,1)\\to (3,3)$\n*   $(1,1)\\to (2,1)\\to (3,2)\\to (3,3)$\n*   $(1,1)\\to (3,1)\\to (3,2)\\to (3,3)$\n*   $(1,1)\\to (3,1)\\to (3,3)$"},{"iden":"sample input 2","content":"4 4\n...#\n....\n..#.\n...."},{"iden":"sample output 2","content":"84\n\nFrom $(1,1)$, the queen can move to $(1,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(3,1)$, or $(4,1)$.\nOne possible path to $(4,4)$ is $(1,1)\\to (3,1)\\to (3,2)\\to (4,3)\\to (4,4)$."},{"iden":"sample input 3","content":"8 10\n..........\n..........\n..........\n..........\n..........\n..........\n..........\n.........."},{"iden":"sample output 3","content":"13701937\n\nFind the count modulo $(10^9+7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}