CF1225E Rock Is Push

你现在在一个 $n×m$ 的迷宫的左上角（即点 $(1,1)$），你的目标是到达迷宫的右下角（即点 $(n,m)$）。一次移动你只能向右或者是向下移动一个单位。比如在点 $(x,y)$ 你可以移动到点 $(x+1,y)$ 或点 $(x,y+1)$。 迷宫中的一些点是岩石，当你移动到一个有岩石的点时岩石将被推到你移动方向的下一个点（你可以把岩石想象成推箱子游戏中的箱子），而如果那个点上也有一个岩石，它就会被按相同方向推的更远，以此类推。（比如当前点右边有连着的十块岩石，你向右走一个点这些岩石就都会被向右推一个点） 这个迷宫被不可移动或是摧毁的墙包围着，石头是不允许被推到墙外或者摧毁墙的。（比如你右边有一个石头，而再往右是墙，你就不能往右移动了） 现在，请你计算出有多少种不同的可以到达终点的方案，由于方案数可能很大，结果请对 $10^9+7$ 取模。两条路径中如果有任意的至少一个点不同，那就认为这两种方案是不同的。

输入第一行是两个正整数 $n,m$ ，表示迷宫的长和宽 $(1\leq n,m\leq2000)$。 然后有 $n$ 行，每行 $m$ 个字符，如果第 $i$ 行的第 $j$ 个字符是 `R`，那就说明点 $(i,j)$ 存在一块岩石，如果是 `.`，那就说明点 $(i,j)$ 是空的。 数据保证出发点 $(1,1)$ 一定是空的。

输出一个整数，表示从 $(1,1)$ 走到 $(n,m)$ 的方案数对 $10^9+7$ 取模的结果。

第一个样例中，不需要移动就能到达终点，所以只有一种路径方案，输出 $1$。 第二个样例中终点被岩石挡住了，无法到达，所以没有方案可以到达终点，输出 $0$。 点击本网址可以看到第三个样例的例图：