#dph. [dp_h]Grid 1
[dp_h]Grid 1
题目描述
有一个由 行和 列组成的网格。用 表示从上往下第 行、从左往右第 列的方格。
对于每个 和 (, ),方格 用字符 描述。如果 是 .
,方格 为空方格;如果 是 #
,方格 是墙方格。保证方格 和 是空方格。
Taro 从方格 出发,通过重复向右或向下移动到相邻的空方格,最终到达 。
找出 Taro 从方格 到 的路径数。由于答案可能非常大,要将计数结果对 取模。
约束条件
- 和 是整数。
- 是
.
或#
。 - 方格 和 是空方格。
输入
输入将从标准输入读取,并具有以下格式:
输出
打印 Taro 从方格 到 的路径数,对 取模。
示例输入1
3 4
...#
.#..
....
示例输出1
3
共有三条路径:
示例输入2
5 2
..
#.
..
.#
..
示例输出2
0
可能没有路径。
示例输入3
5 5
..#..
.....
#...#
.....
..#..
示例输出3
24
示例输入4
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
示例输出4
345263555
请务必对计数结果取模 。