您位于 $$$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