{"problem":{"name":"Grid 1","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_h"},"statements":[{"statement_type":"Markdown","content":"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.\nFor 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.\nTaro will start from Square $(1, 1)$ and reach $(H, W)$ by repeatedly moving right or down to an adjacent empty square.\nFind 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$.\n\n## Constraints\n\n*   $H$ and $W$ are integers.\n*   $2 \\leq H, W \\leq 1000$\n*   $a_{i, j}$ is `.` or `#`.\n*   Squares $(1, 1)$ and $(H, W)$ are empty squares.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$\n$a_{1, 1}$$\\ldots$$a_{1, W}$\n$:$\n$a_{H, 1}$$\\ldots$$a_{H, W}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_h","tags":[],"sample_group":[["3 4\n...#\n.#..\n....","3\n\nThere are three paths as follows:\n![image](https://img.atcoder.jp/dp/grid_0_0_muffet.png)"],["5 2\n..\n#.\n..\n.#\n..","0\n\nThere may be no paths."],["5 5\n..#..\n.....\n#...#\n.....\n..#..","24"],["20 20\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................\n....................","345263555\n\nBe sure to print the count modulo $10^9 + 7$."]],"created_at":"2026-03-03 11:01:14"}}