AT_abc183_e [ABC183E] Queen on Grid

有一个高 $H$ 行、宽 $W$ 列的网格。第 $i$ 行第 $j$ 列的格子 $(i, j)$，如果 $S_{ij}$ 是 `#`，则为墙，否则为道路。 在格子 $(1,1)$ 上放有国际象棋中的皇后棋子。皇后可以沿当前位置向右、向下、右下三个方向的直线上移动，每次移动可以到达不越过墙的任意道路格子，且每次移动算作一步。 请计算皇后从 $(1,1)$ 移动到 $(H,W)$ 的不同路径数，答案对 $10^9+7$ 取模。 注意，若存在某个 $i$，使得第 $i$ 步移动后皇后所在格子的位置不同，则认为两种移动方法不同。

输入以如下格式从标准输入读入。 > $H$ $W$ > $S_{11}\ldots S_{1W}$ > $\vdots$ > $S_{H1}\ldots S_{HW}$

输出皇后从 $(1,1)$ 移动到 $(H,W)$ 的路径数，对 $10^9+7$ 取模。

## 限制 - $2 \leq H, W \leq 2000$ - $S_{ij}$ 只可能为 `#` 或 `.` - $S_{11}$ 和 $S_{HW}$ 均为 `.` ## 样例解释 1 存在如下 $10$ 种移动方法： - $(1,1)\to (1,2)\to (1,3)\to (2,3)\to (3,3)$ - $(1,1)\to (1,2)\to (1,3)\to (3,3)$ - $(1,1)\to (1,2)\to (2,3)\to (3,3)$ - $(1,1)\to (1,3)\to (2,3)\to (3,3)$ - $(1,1)\to (1,3)\to (3,3)$ - $(1,1)\to (2,1)\to (3,1)\to (3,2)\to (3,3)$ - $(1,1)\to (2,1)\to (3,1)\to (3,3)$ - $(1,1)\to (2,1)\to (3,2)\to (3,3)$ - $(1,1)\to (3,1)\to (3,2)\to (3,3)$ - $(1,1)\to (3,1)\to (3,3)$ ## 样例解释 2 从 $(1,1)$ 出发，可以一步到达 $(1,2)$、$(1,3)$、$(2,1)$、$(2,2)$、$(3,1)$、$(4,1)$ 中的任意一个。例如，$(1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4)$ 是到 $(4,4)$ 的一种路径。 ## 样例解释 3 请对路径数取 $10^9+7$ 的模输出。 由 ChatGPT 4.1 翻译