AT_abc379_g [ABC379G] Count Grid 3-coloring

[problemUrl]: https://atcoder.jp/contests/abc379/tasks/abc379_g `1`,`2`,`3`,`?` からなる $ H $ 行 $ W $ 列のグリッド $ S $ が与えられます。上から $ i $ 行目、左から $ j $ 列目の文字は $ S_{i,j} $ です。 $ S $ の各 `?` を `1`,`2`,`3` のいずれかに置き換えて得られるグリッドは `?` の個数を $ q $ として $ 3^q $ 通りありますが、そのうち以下の条件を満たすものはいくつありますか？ $ 998244353 $ で割った余りを出力してください。 - 隣接する（辺を共有する）どの $ 2 $ つのマスにも異なる数字が書かれている。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{1,1}S_{1,2}\ldots\ S_{1,W} $ $ S_{2,1}S_{2,2}\ldots\ S_{2,W} $ $ \vdots $ $ S_{H,1}S_{H,2}\ldots\ S_{H,W} $

答えを出力せよ。

### 制約 - $ 1\leq\ H,W $ - $ H\times\ W\leq\ 200 $ - $ H,W $ は整数 - $ S $ は `1`,`2`,`3`,`?` からなる $ H $ 行 $ W $ 列のグリッド ### Sample Explanation 1 $ S $ の各 `?` を `1`,`2`,`3` のいずれかに置き換えて得られるグリッドのうち、条件を満たすものは以下の $ 6 $ つです。 ``` 12 12 12 13 13 13 21 23 31 21 31 32 ``` ### Sample Explanation 2 $ S $ の各 `?` を `1`,`2`,`3` のいずれかに置き換えて得られるグリッドはすべて条件を満たしません。