E - 皇后在网格上

分值 : $500$ 分

问题描述

给定一个由水平行数 $H$ 和垂直列数 $W$ 组成的网格。

对于网格中的方格 $(i,j)$，如果 $S_{ij}$ 是 #，则称其为墙体，如果 $S_{ij}$ 是 .，则称其为路径。

现在在方格 $(1,1)$ 上有一只皇后，它可以在一步中朝右、下或者右下方向移动任意数量的方格，在不越过墙体方格的情况下到达一个路径方格。

从方格 $(1,1)$ 到方格 $(H,W)$ 有多少种不同的移动方式？将结果模 $(10^9+7)$ 输出。

这里，当且仅当存在 $i$，使得两种方式在第 $i$ 步后皇后的位置不同，才认为它们是不同的移动方式。

约束

• $2 \leq H,W \leq 2000$
• $S_{ij}$ 是 # 或者 .
• $S_{11}$ 和 $S_{HW}$ 是 .

输入

输入从标准输入中给出，格式如下：

$H$ $W$

$S_{11}\ldots S_{1W}$

$\vdots$

$S_{H1}\ldots S_{HW}$

输出

输出在从方格 $(1,1)$ 到方格 $(H, W)$ 的过程中，皇后的移动方式数，结果需对 $(10^9+7)$ 取模后输出。

3 3
...
.#.
...

10

有 $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)$

4 4
...#
....
..#.
....

84

从 $(1,1)$ 出发，皇后可以移动到 $(1,2)$，$(1,3)$，$(2,1)$，$(2,2)$，$(3,1)$，或者 $(4,1)$。

一个到达 $(4,4)$ 的可能路径是 $(1,1)\to(3,1)\to(3,2)\to(4,3)\to(4,4)$。

8 10
..........
..........
..........
..........
..........
..........
..........
..........

13701937

将结果模 $(10^9+7)$ 后输出。