#include #include using namespace std; using mint = atcoder::modint998244353; #define rep(i, a, b) for (int i = (a); i < (b); i++) int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; vector s(h); rep(i, 0, h) cin >> s[i]; int N = h * w; unordered_map dp, ndp; dp.reserve(1 << 16); ndp.reserve(1 << 16); // 初期状態:flattened indices を key にパック (first*N + second) dp[(long long)1 * N + w] = 1; rep(dist, 1, h + w - 3) { ndp.clear(); for (auto &it : dp) { long long key = it.first; mint v = it.second; int p = key / N, q = key % N; int ai = p / w, aj = p % w; int bi = q / w, bj = q % w; rep(i, 0, 2) rep(j, 0, 2) { int nai = ai + i, naj = aj + 1 - i; int nbi = bi + j, nbj = bj + 1 - j; if (nai >= h || naj >= w || nbi >= h || nbj >= w) continue; if (s[nai][naj] == '#' || s[nbi][nbj] == '#') continue; if (nai == nbi && naj == nbj) continue; if (nai == bi && naj == bj) continue; if (ai == nbi && aj == nbj) continue; int np = nai * w + naj; int nq = nbi * w + nbj; long long newkey = (long long)np * N + nq; ndp[newkey] += v; } } dp.swap(ndp); } if (dp.empty()) { cout << 0 << "\n"; } else { for (auto &it : dp) { cout << it.second.val() << "\n"; } } return 0; }