You are at the top left cell (1,1)(1,1) of an n×mn×m labyrinth. Your goal is to get to the bottom right cell (n,m)(n,m). You can only move right or down, one cell per step. Moving right from a cell (x,y)(x,y) takes you to the cell (x,y+1)(x,y+1), while moving down takes you to the cell (x+1,y)(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 109+7109+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.

Input

The first line contains two integers n,mn,m — dimensions of the labyrinth (1≤n,m≤20001≤n,m≤2000).

Next nn lines describe the labyrinth. Each of these lines contains mm characters. The jj-th character of the ii-th of these lines is equal to "R" if the cell (i,j)(i,j) contains a rock, or "." if the cell (i,j)(i,j) is empty.

It is guaranteed that the starting cell (1,1)(1,1) is empty.

Output

Print a single integer — the number of different legal paths from (1,1)(1,1) to (n,m)(n,m)modulo 109+7109+7.

Examples

Input

1 1
.

Output

1

Input

2 3
...
..R

Output

0

Input

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

Output

4

题目大意：给你一张n*m的地图，其中如果(i,k)为'R'说明该点为石头，否则即为空地。当一个人走到'R'的地方时，会把R推向(i,k+1)或者(i+1,k) {取决于人来的方向},石头不能推出界外也就是说到边界之后你就推不动了。问从左上角(1,1)到右下角(n,m)的路线总数。

题目思路：

我们从(n,m)向(1,1) 进行dp，于是左上方石头的状态与我们无关。（因为我能推到哪只与我右方和下方的石头有关）

随后我们分行进行dp

我们假设点 (i,k)，到达点(i,k)的方案即为 该点右边的点（最后一步从下方过来）+该点下方的点（最后一步从右方过来）。

但是由于有石头的存在所以不是所有的点都可以对(i,k)这个点进行转移。如果从右边来的话，石头推到边界就推不动了，所以石头会占用一部分空间：

所以我们记录：每个点右方和下方的 '.' 的数量，即最大可以转移的区间长度，随后我们进行dp就可以了，使用一个前缀和优化：

最终dp状态转移方程：

其中r[i][k]分别表示 右方可用空间与左方可用空间

AC：

#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#include <queue>
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e6+5;
const ll INF=100000000000000005;
const double eps=1e-11;
using namespace std;
ll n,m;
char mp[2005][2005];//map
ll sum[2005][2005][2];//zero for up,one for left
ll dp[2005][2005][2];// zero for up ,one for left
ll r[2005][2005][2];//zero for row one for column
void restart()
{
    for(int i=1;i<=n;i++)
        for(int k=m;k>=1;k--)
            r[i][k][1]=r[i][k+1][1]+(mp[i][k]=='.');
    for(int i=n;i>=1;i--)
        for(int k=1;k<=m;k++)
            r[i][k][0]=r[i+1][k][0]+(mp[i][k]=='.');
   /* for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++)
            printf("坐标为(%d,%d)的右边有%lld个 下边有%lld个\n",i,k,sum[i][k][1],sum[i][k][0]);*/
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",mp[i]+1);
    restart();
    if(mp[n][m]=='R') {
        printf("0\n");return 0;
    }
    if(n==1&&m==1){
            printf("1\n");return 0;}
    dp[n][m][0]=dp[n][m][1]=1;
    sum[n][m][0]=sum[n][m][1]=1;
    for(int i=n;i>=1;i--)
    {
        for(int k=m;k>=1;k--)
        {
            if(i==n&&k==m) continue;
            ll temp=r[i][k+1][1];//右方空余多少
            dp[i][k][0]=(sum[i][k+1][1]-sum[i][k+temp+1][1]+mod)%mod;//右方的路线都从下方转移而来
            temp=r[i+1][k][0];//下方空余多少
            dp[i][k][1]=(sum[i+1][k][0]-sum[i+temp+1][k][0]+mod)%mod;//下方的路线都从右方转移而来
            sum[i][k][0]=(sum[i+1][k][0]+dp[i][k][0])%mod;//更新一下
            sum[i][k][1]=(sum[i][k+1][1]+dp[i][k][1])%mod;
        }
    }
    printf("%lld\n",(dp[1][1][1]+dp[1][1][0])%mod);
    return 0;
}