← 返回题目列表

AtCoder · abc183_e

E. 网格女王

中文机器翻译题面 查看原题

分数: 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).