CF1225E.Rock Is Push

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.

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

迷宫中某些单元格包含石块。当你移动到一个有石块的单元格时，该石块会被沿你移动的方向推入下一个单元格。如果下一个单元格中也有石块，则它也会被继续推动，依此类推。

迷宫四周被不可穿透的墙壁包围，因此任何会导致你自身或任意石块移出迷宫边界的移动均视为非法。

计算从起点到终点的所有合法路径数目，结果对 $10^9 + 7$ 取模。若两条路径中至少存在一个被其中一条路径访问而未被另一条路径访问的单元格，则认为这两条路径不同。

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.

第一行包含两个整数 $n, m$ —— 迷宫的维度（$1 \leq n, m \leq 2000$）。

接下来的 $n$ 行描述迷宫。每行包含 $m$ 个字符。在这些行中，第 $i$ 行的第 $j$ 个字符为 "R" 表示单元格 $(i, j)$ 中有一块岩石，为 "." 表示单元格 $(i, j)$ 为空。

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

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

输出一个整数——从 $(1, 1)$ 到 $(n, m)$ 的不同合法路径数目对 $10^9 + 7$ 取模的结果。

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

在第一个样例中，我们无法（且无需）移动，因此唯一的一条路径仅包含单个格子 $(1, 1)$。

在第二个样例中，目标格子被阻挡，无法到达。

第三个样例的示意图可在此处查看：https://assets.codeforces.com/rounds/1225/index.html