Rock Is Push

题意翻译

你现在在一个$n×m$的迷宫的左上角（即点$(1,1)$），你的目标是到达迷宫的右下角（即点$(n,m)$）。一次移动你只能向右或者是向下移动一个单位。比如在点$(x,y)$你可以移动到点$(x+1,y)$或点$(x,y+1)$ 迷宫中的一些点是岩石，当你移动到一个有岩石的点时岩石将被推到你移动方向的下一个点（你可以把岩石想象成推箱子游戏中的箱子），而如果那个点上也有一个岩石，它就会被按相同方向推的更远，以此类推（比如当前点右边有连着的十块岩石，你向右走一个点这些岩石就都会被向右推一个点） 这个迷宫被不可移动或是摧毁的墙包围着，石头是不允许被推到墙外或者摧毁墙的。（比如你右边有一个石头，而再往右是墙，你就不能往右移动了） 现在，请你计算出有多少种不同的可以到达终点的方案，由于方案数可能很大，结果请对$10^9+7$取模。两条路径中如果有任意的至少一个点不同，那就认为这两种方案是不同的。 ### 输入格式 输入第一行是两个正整数$n,m$，表示迷宫的长和宽$(1≤n,m≤2000)$ 然后有$n$行，每行$m$个字符，如果第$i$行的第$j$个字符是"$R$"，那就说明点$(i,j)$存在一块岩石，如果是"."，那就说明点$(i,j)$是空的 数据保证出发点$(1,1)$一定是空的 ### 输出格式 输出一个整数，表示从$(1,1)$走到$(n,m)$的方案数对$10^9+7$取模的结果。 ### 样例说明 第一个样例中，不需要移动就能到达终点，所以只有一种路径方案，输出$1$ 第二个样例中终点被岩石挡住了，无法到达，所以没有方案可以到达终点，输出$0$ 点击本网址可以看到第三个样例的例图 https://assets.codeforces.com/rounds/1225/index.html

题目描述

You are at the top left cell $ (1, 1) $ of an $ n \times m $ labyrinth. Your goal is to get to the bottom right cell $ (n, m) $ . You can only move right or down, one cell per step. Moving right from a cell $ (x, y) $ takes you to the cell $ (x, y + 1) $ , while moving down takes you to the cell $ (x + 1, y) $ . Some cells of the labyrinth contain rocks. When you move to a cell with rock, the rock is pushed to the next cell in the direction you're moving. If the next cell contains a rock, it gets pushed further, and so on. The labyrinth is surrounded by impenetrable walls, thus any move that would put you or any rock outside of the labyrinth is illegal. Count the number of different legal paths you can take from the start to the goal modulo $ 10^9 + 7 $ . Two paths are considered different if there is at least one cell that is visited in one path, but not visited in the other.

输入输出格式

输入格式

The first line contains two integers $ n, m $ — dimensions of the labyrinth ( $ 1 \leq n, m \leq 2000 $ ). Next $ n $ lines describe the labyrinth. Each of these lines contains $ m $ characters. The $ j $ -th character of the $ i $ -th of these lines is equal to "R" if the cell $ (i, j) $ contains a rock, or "." if the cell $ (i, j) $ is empty. It is guaranteed that the starting cell $ (1, 1) $ is empty.

输出格式

Print a single integer — the number of different legal paths from $ (1, 1) $ to $ (n, m) $ modulo $ 10^9 + 7 $ .

输入输出样例

输入样例 #1

1 1
.

输出样例 #1

1

输入样例 #2

2 3
...
..R

输出样例 #2

0

输入样例 #3

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

输出样例 #3

4

说明

In the first sample case we can't (and don't have to) move, hence the only path consists of a single cell $ (1, 1) $ . In the second sample case the goal is blocked and is unreachable. Illustrations for the third sample case can be found here: <https://assets.codeforces.com/rounds/1225/index.html>