cave WA

// Problem : Problem 1. Cave Paintings
// Contest : USACO 2020 January Contest, Platinum
// URL : http://usaco.org/index.php?page=viewproblem2&cpid=996
// Memory Limit : 256 MB
// Time Limit : 4000 ms
// Powered by CP Editor (https://github.com/cpeditor/cp-editor)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9 + 7;

inline int add(int x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
}
inline int mult(int x, int y) {
    return (ll)x * y % mod;
}

const int N = 1010;

int ans;
int R, C;
int grid[N][N];
int prod[N*N];
int val[N*N];

inline int conv(int r, int c) {
    return r*C + c;
}

struct DSU {
    int p[N*N], rank[N*N], maxrow[N*N];
    inline int get(int x) {
        return p[x] == x ? x : (p[x] = get(p[x]));
    }
    inline bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        p[y] = x;
        maxrow[x] = max(maxrow[x], maxrow[y]);
        return true;
    }
} dsu;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef _DEBUG
    freopen("cave.in", "r", stdin);
    freopen("cave.out", "w", stdout);
    #endif
    cin >> R >> C;
    for (int i = 0; i < N*N; ++i) {
        dsu.p[i] = i;
        dsu.rank[i] = 0;
        dsu.maxrow[i] = i/C;
        val[i] = 0;
    }
    for (int r = R-1; r >= 0; --r) {
        for (int c = 0; c < C; ++c) {
            char ch;
            cin >> ch;
            grid[r][c] = ch == '.' ? 0 : 1;
        }
    }
    ans = 1;
    for (int row = 1; row < R; ++row) {
        //cout << "row="<<row<<"\n";
        for (int col = 0; col < C; ++col) {
            if (grid[row][col]) continue;
            int l = col;
            while (col < C && !grid[row][col]) ++col;
            // [l, r] empty
            //cout << "["<<l<<","<<col-1<<"]\n";
            int prd = 1;
            for (int x = l; x < col; ++x) {
                int id1 = dsu.get(conv(row, x));
                dsu.unite(conv(row, l), id1);
                if (!grid[row-1][x]) {
                    int id2 = dsu.get(conv(row-1, x));
                    if (id2 != id1) {
                        if (dsu.maxrow[id2] == row) {
                            //cout<<"x="<<x<<" prodbelow="<<prod[id2]<<"\n";
                            prd = prod[id2];
                            dsu.unite(id1, id2);
                        } else {
                            //cout<<"x="<<x<<" valbelow="<<val[id2]<<"\n";
                            prd = mult(prd, val[id2]);
                            dsu.unite(id1, id2);
                        }
                    }
                }
            }
            //cout << "val="<<add(prd,1)<<"\n";
            int id = dsu.get(conv(row, l));
            prod[id] = prd;
            val[id] = add(prd, 1);
            --col;
        }
        for (int col = 0; col < C; ++col) {
            if (grid[row-1][col]) continue;
            int l = col;
            while (col < C && !grid[row-1][col]) ++col;
            int id = dsu.get(conv(row-1, l));
            if (dsu.maxrow[id] == row-1) {
                // wasnt brought up to current row
                // which means it is isolated
                ans = mult(ans, val[id]);
                val[id] = 1;
            }
            --col;
        }
    }
    cout << ans << '\n';
}