2805.cpp

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    using ll = long long;
    vector<vector<ll>> has, dp;
    vector<pair<int,int>> chng;
    has = dp = vector<vector<ll>>(n, vector<ll>(m, 0));
    for (int i = 0; i < n; ++i){
        s[i].resize(m);
        cin >> s[i];
        for (int j = 0; j < m; ++j){
            if (s[i][j] == '1') chng.push_back({i,j});
            if (i == 0 and j == 0){
                has[i][j] = s[i][j] == '0';
                continue;
            }
            if (i == 0 and j){
                has[i][j] = has[i][j-1] or s[i][j] == '0';
                continue;
            }
            if (i and j == 0){
                has[i][j] = has[i-1][j] or s[i][j] == '0';
                continue;
            }
            has[i][j] = has[i-1][j] or has[i][j-1] or s[i][j] == '0';
        }
    }
    for (auto a : chng){
        for (int i = 0; i <= a.first; ++i){
            for (int j = 0; j <= a.second; ++j){
                if (s[i][j] == '0'){
                    cout << 0 << '\n';
                    return 0;
                }
                s[i][j] = '1';
            }
        }
    }
    // for (auto a: s){
    //     cout << a;
    //     cout << '\n';
    // }
    // cout << "oi" << endl;
    const int mod = 1e9+7;
    dp[0][0] = s[0][0] != '0';
    for (int i = 1; i < m; ++i){
        if (s[0][i] == '1') dp[0][i] = 1;
        else
            dp[0][i] = dp[0][i-1] + !has[0][i];
    }
    for (int i = 1; i < n; ++i) {
        if (s[i][0] == '1') dp[i][0] = 1;
        else dp[i][0] = dp[i-1][0] + !has[i][0];
    }
    for (int i = 1; i < n; ++i){
        for (int j = 1; j < m; ++j){
            if (s[i][j] == '1') dp[i][j] = 1;
            else    dp[i][j] = (dp[i-1][j]*dp[i][j-1] + !has[i][j]) % mod;
        }
    }

    // for (auto a: dp){
    //     for (auto b : a){
    //         cout << b;
    //     }
    //     cout << '\n';
    // }
    cout << dp[n-1][m-1] << '\n';
    return 0;
}