皇后的走法

题目描述

有一个纵向 $H$ 格、横向 $W$ 格的网格。 从上数第 $i$ 行、从左数第 $j$ 列的格子 $(i,j)$，当 $S_{ij}$ 为 # 时是墙壁，为 . 时是道路。

在格子 $(1,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)$ 取模后的值。

样例

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$ 步可以移动到 $(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)$ 取模后求出。

数据范围

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