← 返回题目列表

AtCoder · dp_h

H. 网格 1

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

分数: 100 点

问题陈述

有一个网格 H 水平行和 W 垂直列。 让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。

对于每个 i 和 j (1 \leq i \leq H, 1 \leq j \leq W),方形 (i, j) 由字符描述 a_{i, j}。 如果 a_{i, j} is .,方形 (i, j) 是一个空方块;如果 a_{i, j} is #,方形 (i, j) 是一个墙方块。 保证正方形 (1, 1) 和 (H, W) 是空方块。

太郎将从广场开始 (1, 1) 并达到 (H, W) 通过重复向右或向下移动到相邻的空方块。

从 Square 中找出太郎的路径数 (1, 1) to (H, W)。 由于答案可能非常大,因此求模数 10^9 + 7.

约束

  • H 和 W 是整数。
  • 2 \leq H, W \leq 1000
  • a_{i, j} is . or #.
  • 正方形 (1, 1) 和 (H, W) 是空方块。

输入

输入由标准输入按以下格式给出:

H W
a_{1, 1}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}

输出

打印 Square 中 Taro 的路径数 (1, 1) to (H, W),模数 10^9 + 7.


示例输入 1

3 4
...#
.#..
....

示例输出 1

3

共有以下三个路径:


示例输入 2

5 2
..
#.
..
.#
..

示例输出 2

0

可能没有路径。


示例输入 3

5 5
..#..
.....
#...#
.....
..#..

示例输出 3

24

示例输入 4

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

示例输出 4

345263555

请务必打印模数计数 10^9 + 7.