分数: 500 点
问题陈述
我们有一个网格 H 水平行和 W 垂直的方块列。
广场 (i,j),位于 i从顶部开始的第行和 j从左边算起的第列是 墙 if S_{ij} is # 和 路 if S_{ij} is ..
广场上有一个皇后,即棋子 (1, 1)。一次移动,它可以将任意数量的方格向右、向下或对角地右下移动到道路方格,而无需跳过墙壁方格。
女王可以通过多少种方式从Square出行 (1, 1) 到广场 (H, W)?求计数模数 (10^9+7).
这里,两种出行方式被认为是不同的当且仅当存在 i 这样皇后的位置就在 i-th 移动在这两种方面是不同的。
约束
- 2 \leq H,W \leq 2000
- S_{ij} is
#or.. - S_{11} 和 S_{HW} 是
..
输入
输入由标准输入按以下格式给出:
H W
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}
输出
打印路数,模数 (10^9+7),其中女王可以从 Square 出发 (1, 1) 到广场 (H, W).
示例输入 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) is (1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4).
示例输入 3
8 10 .......... .......... .......... .......... .......... .......... .......... ..........
示例输出 3
13701937
求计数模数 (10^9+7).