#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include #include #define pass (void)0 #define INF (1<<30)-1 #define INFLL (1LL<<60)-1 using namespace std; using namespace atcoder; using mint = modint998244353; using ll = long long; // グリッドの幅と高さ int H, W; // 座標を一意に識別するための関数 ll IDX(int h1, int w1, int h2, int w2) { return w1 + h1 * W + w2 * H * W + h2 * W * H * W; } // 座標の復元 tuple IDXR(ll n) { int w1 = n % W; int h1 = (n / W) % H; int w2 = (n / (H * W)) % W; int h2 = (n / (W * H * W)); return {h1, w1, h2, w2}; } int main() { cin >> H >> W; vector S(H); for (int i=0; i> S[i]; unordered_map dp; dp[IDX(1, 0, 0, 1)] = 1; for (int i = 0; i < H + W - 3; ++i) { unordered_map ndp; for (const auto& [key, val] : dp) { auto [h1, w1, h2, w2] = IDXR(key); // w1+1, w2+1への移動 if (w1 + 1 < W && w2 + 1 < W && S[h1][w1 + 1] == '.' && S[h2][w2 + 1] == '.') { ndp[IDX(h1, w1 + 1, h2, w2 + 1)] = (ndp[IDX(h1, w1 + 1, h2, w2 + 1)] + val); } // h1+1, h2+1への移動 if (h1 + 1 < H && h2 + 1 < H && S[h1 + 1][w1] == '.' && S[h2 + 1][w2] == '.') { ndp[IDX(h1 + 1, w1, h2 + 1, w2)] = (ndp[IDX(h1 + 1, w1, h2 + 1, w2)] + val); } // w1+1, h2+1への移動 if (w1 + 1 < W && h2 + 1 < H && S[h1][w1 + 1] == '.' && S[h2 + 1][w2] == '.' && ((h1 == H - 1 && w1 + 1 == W - 1) || make_pair(h1, w1 + 1) != make_pair(h2 + 1, w2))) { ndp[IDX(h1, w1 + 1, h2 + 1, w2)] = (ndp[IDX(h1, w1 + 1, h2 + 1, w2)] + val); } // h1+1, w2+1への移動 if (h1 + 1 < H && w2 + 1 < W && S[h1 + 1][w1] == '.' && S[h2][w2 + 1] == '.' && ((h1 + 1 == H - 1 && w1 == W - 1) || make_pair(h1 + 1, w1) != make_pair(h2, w2 + 1))) { ndp[IDX(h1 + 1, w1, h2, w2 + 1)] = (ndp[IDX(h1 + 1, w1, h2, w2 + 1)] + val); } } dp = move(ndp); } cout << dp[IDX(H - 1, W - 1, H - 1, W - 1)].val() << endl; return 0; }