CF1225E Rock Is Push

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

无

无

第一个样例中，不需要移动就能到达终点，所以只有一种路径方案，输出$1$ 第二个样例中终点被岩石挡住了，无法到达，所以没有方案可以到达终点，输出$0$ 点击本网址可以看到第三个样例的例图 https://assets.codeforces.com/rounds/1225/index.html