{"problem":{"name":"Queen on Grid","description":{"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc183_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $2 \\leq H,W \\leq 2000$\n*   $S_{ij}$ is `#` or `.`.\n*   $S_{11}$ and $S_{HW}$ are `.`.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc183_e","tags":[],"sample_group":[["3 3\n...\n.#.\n...","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)$"],["4 4\n...#\n....\n..#.\n....","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)$."],["8 10\n..........\n..........\n..........\n..........\n..........\n..........\n..........\n..........","13701937\n\nFind the count modulo $(10^9+7)$."]],"created_at":"2026-03-03 11:01:14"}}