← 返回题目列表

Codeforces · 1225/E

E. 摇滚是推

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

您位于 $$$n \times m$$$ 迷宫的左上角单元格 $$$(1, 1)$$$。您的目标是到达右下角的单元格$$$(n, m)$$$。您只能向右或向下移动,每步一个单元格。从单元格 $$$(x, y)$$$ 向右移动会将您带到单元格 $$$(x, y + 1)$$$,而向下移动则会将您带到单元格 $$$(x + 1, y)$$$。

迷宫的一些单元格含有岩石。当您移动到带有岩石的单元格时,岩石会被推到您移动方向的下一个单元格。如果下一个单元格包含一块岩石,它就会被推得更远,依此类推。

迷宫被无法穿透的墙壁包围,因此任何将你或任何岩石移出迷宫的行为都是非法的。

计算从起点到目标可以采取的不同合法路径的数量,以 $$$10^9 + 7$$$ 为模。如果一条路径中至少有一个单元被访问,但另一条路径中未被访问,则两条路径被认为是不同的。

输入

第一行包含两个整数 $$$n, m$$$ — 迷宫的尺寸 ($$$1 \leq n, m \leq 2000$$$)。

接下来的 $$$n$$$ 行描述了迷宫。这些行中的每一行都包含 $$$m$$$ 字符。如果单元格 $$$(i, j)$$$ 包含岩石或“.”,则这些行中第 $$$i$$$ 的第 $$$j$$$ 个字符等于“R”。如果单元格 $$$(i, j)$$$ 为空。

保证起始单元格 $$$(1, 1)$$$ 为空。

输出

打印单个整数 - 从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 模 $$$10^9 + 7$$$ 的不同合法路径的数量。

示例

输入 #1

1 1
.

输出 #1

1

输入 #2

2 3
...
..R

输出 #2

0

输入 #3

4 4
...R
.RR.
.RR.
R...

输出 #3

4

注意

在第一个示例中,我们不能(也不必)移动,因此唯一的路径由单个单元格 $$$(1, 1)$$$ 组成。

在第二个示例案例中,目标被阻止并且无法到达。

第三个示例案例的插图可以在这里找到:https://assets.codeforces.com/rounds/1225/index.html