AT_abc379_g [ABC379G] Count Grid 3-coloring

给定一个由 `1`、`2`、`3`、`?` 组成的 $H$ 行 $W$ 列的网格 $S$。第 $i$ 行第 $j$ 列的字符为 $S_{i,j}$。 将 $S$ 中的每个 `?` 替换为 `1`、`2`、`3` 中的任意一个，可以得到 $3^q$ 种不同的网格（其中 $q$ 为 `?` 的个数）。在这些网格中，有多少种满足以下条件？请输出对 $998244353$ 取模的结果。 - 任意两个相邻（共享边）的格子中，数字都不相同。

输入以如下格式从标准输入读入。 > $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$ 列 ## 样例解释 1 将 $S$ 中的每个 `?` 替换为 `1`、`2`、`3` 后，满足条件的网格有如下 $6$ 种： ``` 12 12 12 13 13 13 21 23 31 21 31 32 ``` ## 样例解释 2 将 $S$ 中的每个 `?` 替换为 `1`、`2`、`3` 后，没有任何一种网格满足条件。 由 ChatGPT 4.1 翻译