问题描述

我们有一个 $H$ 行 $W$ 列的正方形网格。如果第 $i$ 行第 $j$ 列的正方形是墙壁，那么记为 $S_{ij}$ 为 #；如果是道路，那么记为 $S_{ij}$ 为 .。

现在有一个皇后，初始位置在 $(1,1)$ 这个方格上。每次移动，皇后可以向右、向下或者向右下方斜对角线方向移动任意数量的方格，但是不能越过墙壁方格。

问皇后从起始位置 $(1,1)$ 移动到目标位置 $(H,W)$，共有多少种移动方式？输出对 $(10^9+7)$ 取模之后的结果。

这里，如果两种移动方式在某一步后皇后的位置不同，那么这两种移动方式就被认为是不同的。

约束条件

• $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)$ 取模之后的结果。

示例输入 1

3 3
...
.#.
...

示例输出 1

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

示例输入 2

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

示例输出 2

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

示例输入 3

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

示例输出 3

13701937

对 $(10^9+7)$ 取模之后的结果为 13701937。