AT_arc157_d [ARC157D] YY Garden

[problemUrl]: https://atcoder.jp/contests/arc157/tasks/arc157_d $ H $ 行 $ W $ 列のマス目の各マスに `X`, `Y` のいずれかの文字が書かれています． 上から $ i $ 行目，左から $ j $ 列目のマスを $ (i,\ j) $ で表します． マス目に書かれている文字は $ H $ 個の文字列 $ S_1,\ S_2,\ \dots,\ S_H $ によって与えられ，$ S_i $ の $ j $ 文字目がマス $ (i,\ j) $ に書かれた文字を表します． 隣り合う各行および各列の間に，マス目全体を横断（縦断）するように柵を設置できます． 柵同士は交差しても構いません． 柵の設置後に，「あるマスから始めて上下左右に隣接するマスへの移動を繰り返すことで，柵を越えずに到達可能なマス全体」を**区画**と定義します． （出力例 1 の説明も参考にしてください．） 柵の設置方法は全部で $ 2^{H-1}\ \times\ 2^{W-1} $ 通りありますが，そのうち次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください． **条件:** 各区画には `Y` が書かれたマスがちょうど $ 2 $ 個含まれている．

入力は以下の形式で標準入力から与えられる． > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

条件を満たす柵の設置方法の総数を $ 998244353 $ で割った余りを出力せよ．

### 制約 - $ 1\ \leq\ H\ \leq\ 2000 $ - $ 1\ \leq\ W\ \leq\ 2000 $ - $ S_i\ (1\ \leq\ i\ \leq\ H) $ は `X`, `Y` からなる長さ $ W $ の文字列である． ### Sample Explanation 1 柵の設置方法として，以下の $ 8 $ 通りがあります． ``` X Y Y X|Y Y X Y|Y X|Y|Y | | | | Y X Y Y|X Y Y X|Y Y|X|Y X Y Y X|Y Y X Y|Y X|Y|Y ----- -+--- ---+- -+-+- Y X Y Y|X Y Y X|Y Y|X|Y ``` たとえば，$ 2,\ 3 $ 列目の間に柵を設置した場合，区画は ``` XY YX ``` ``` Y Y ``` であり，それぞれにちょうど $ 2 $ 個の `Y` が含まれているので，条件を満たします． また，$ 1,\ 2 $ 行目の間と $ 1,\ 2 $ 列目の間に柵を設置した場合，区画は ``` X ``` ``` YY ``` ``` Y ``` ``` XY ``` となり，$ 2 $ つ目の区画以外にはちょうど $ 2 $ 個の `Y` が含まれていないので，条件を満たしません． ### Sample Explanation 2 どのように柵を設置しても条件を満たしません． ### Sample Explanation 3 条件を満たす柵の設置方法の総数を $ 998244353 $ で割った余りを出力してください．