ABC311F TLE

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

constexpr int mod = 998244353;

int main(int argc, char **argv)
{
    int n, m;
    cin >> n >> m;
    vector<string> vs(n);
    for (auto &s : vs)
        cin >> s;

    ll ans = 0;
    auto get_first_row = [&](int col) {
        for (int i = 0; i < n; ++i)
            if (vs[i][col] == '#')
                return i;
        return n;
    };
    vector<int> fbs(m, n);
    for (int i = 0; i < m; ++i)
        fbs[i] = get_first_row(i);

    map<pii, ll> cache;
    function<ll(int, int)> search = [&](int col, int fb) {
        if (cache.count({col, fb}))
            return cache[{col, fb}];
        if (col == -1)
            return 1ll;
        int lb = fb, ub = fbs[col] + 1;
        ll ans = 0;
        for (int i = ub - 1; i >= lb; --i) {
            ans = (ans + search(col - 1, max(i - 1, 0))) % mod;
            cache[{col, i}] = ans;
        }

        // dbg(col, fb, ans);
        return cache[{col, fb}] = ans;
    };

    ans = search(m - 1, 0);
    cout << ans << endl;
    return 0;
};