#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using v = vector<ll>;
void dpA(){
    int n;
    cin >> n;
    auto h = vector<ll>(n,0);
    for(ll i =0;i<n;i++) cin >> h[i];

    auto dp = vector<ll>(n+2,1e9);
    
    dp[0] = 0;
    dp[1] = 0;
    for(ll i=1;i<n;i++){
        if(i>=2) dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2])); 
        else if(i>=1) dp[i] = dp[i-1] + abs(h[i]-h[i-1]);
    }
    cout << dp[n-1];
}

void dpB(){
    ll n,k;
    cin >> n >> k;
    auto h = vector<ll>(n+1,0);
    for(ll i=0;i<n;i++) cin >> h[i];

    auto dp = vector<ll>(100000,1e9);
    dp[0] = 0;
    for(ll i=0;i<n;i++){
        for(ll j=1;j<=k;j++){
           if(i+j<=n) dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j]-h[i]));
        }
    }
    cout << dp[n-1];
}

void dpC(){
    ll n; cin >> n;
    vector<v> a(n,v(3,0));
    for(ll i=0;i<n;i++) cin >> a[i][0] >> a[i][1] >> a[i][2];

    auto dp = vector<v>(n+1,v(3,0));

    for(ll i=0;i<n;i++)
        for(ll today=0;today<3;today++)
            for(ll oday=0;oday<3;oday++)
                if(today!=oday) 
                    dp[i+1][today] = max(dp[i+1][today],dp[i][oday] + a[i][today]);
    
    cout << max(dp[n][0],max(dp[n][1],dp[n][2]));
   
    
}

void dpD(){
    ll N,W;
  	cin >> N >> W;
    auto ww = v(N,0);
    auto vv = v(N,0);
    for(ll i=0;i<N;i++) cin >> ww[i] >> vv[i];

    auto dp = vector<v>(N+1,v(W+1,0));
    
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j <= W; j++)
        {

            if(j-ww[i]>=0) dp[i+1][j] = max(dp[i][j],dp[i][j-ww[i]]+vv[i]);
            else dp[i+1][j] = dp[i][j];
        }    
    }
    cout << dp[N][W];
}

void dpE(){
    ll N,W;
  	cin >> N >> W;
    auto ww = v(N,0);
    auto vv = v(N,0);
    for(ll i=0;i<N;i++) cin >> ww[i] >> vv[i];

    auto dp = vector<v>(N+1,v(1e5+100,1LL<<60));
    dp[0][0] = 0;
  
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j <=1e5; j++)
        {
            if(j+vv[i]<=1e5) dp[i+1][j+vv[i]] = min(dp[i+1][j+vv[i]],dp[i][j]+ww[i]);  
            dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
        }    
    }
  
    ll ans = 0;
    for(auto i=0;i<=1e5;i++){
        if(dp[N][i] <=W){
            ans = i;
        }
    }
    cout << ans;
}

void dpF(){
    string s,t;
    cin >> s >> t;
    auto dp = vector<v>(s.size()+1,v(t.size()+1,0));

    for(ll i=0;i<s.size();i++)
        for(ll j=0;j<t.size();j++){
            if(s[i]==t[j]) dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j]);
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1]);
        }
  	
    ll i = s.size();
    ll j = t.size();
    string res="";
    while (i>0&&j>0)
    {
        if(dp[i][j]==dp[i-1][j]){
            i--;
        }else if(dp[i][j]==dp[i][j-1]){
            j--;
        }else{
          	res = s[i-1]+res;
            i--;
          	j--;          
        }
    }
    cout << res;
}


class dpG{
    vector<ll> dp;
    vector<v> G;
    ll N;
    ll M;

    void input(){
        cin >> N >> M;
    }

    ll rec(ll i){
        if(dp[i]!=-1) return dp[i];
        
        ll _max=0;
        for(auto nv:G[i]){
            _max = max(_max,rec(nv)+1);
        }
        return dp[i] = _max;
    }

    public:
    ll operator()(){
        input();
        dp.resize(N,-1);
        G.resize(N);
        for(ll i=0;i<M;i++){
            ll x,y;
            cin >> x >> y;
            x--; y--;
            G[x].push_back(y);
        }

        ll _max = 0;
        for(ll i=0;i<N;i++) _max = max(_max,rec(i)); 
        return _max;
    }
};

class dpH{
    const ll INF = 1e9+7;
    vector<v> dp;
        public: dpH(){
        ll H,W;
        cin >> H >> W;
        auto a = vector<vector<char>>(H+1,vector<char>(W+1,'#'));
        for(ll i=0;i<H;i++)
            for(ll j=0;j<W;j++)
                cin >> a[i][j];
          
        dp.resize(1001,v(1001,0));
        dp[0][0] = 1;
        for(ll i=0;i<H;i++)
            for(ll j=0;j<W;j++){
                if(a[i+1][j]=='.') {
                  dp[i+1][j] = dp[i+1][j]+dp[i][j];
                  dp[i+1][j] %=INF; 
                }
                if(a[i][j+1]=='.') {
                  dp[i][j+1] = dp[i][j+1]+dp[i][j];
                  dp[i][j+1] %=INF;
                } 
            }
        cout << dp[H-1][W-1];
    }

};

int main(){
    dpH();
    return 0;
}

Measured memory_bytes: 9088