AT_abc295_h [ABC295Ex] E or m

有一个 $N$ 行 $M$ 列的网格 $A$，初始时所有格子上的数字都是 $0$。 接下来进行如下操作： - 对于每个满足 $1 \le i \le N$ 的整数 $i$，可以将 $A$ 的第 $i$ 行从左边起连续的 $0$ 个或更多格子的数字变为 $1$。 - 对于每个满足 $1 \le j \le M$ 的整数 $j$，可以将 $A$ 的第 $j$ 列从上边起连续的 $0$ 个或更多格子的数字变为 $1$。 通过上述操作能够得到的所有 $A$ 的集合记为 $S$。 现在给定一个由 `0`、`1`、`?` 组成的 $N$ 行 $M$ 列的网格 $X$。 将 $X$ 中的每个 `?` 替换为 `0` 或 `1`，一共可以得到 $2^q$ 个不同的网格（$q$ 为 $X$ 中 `?` 的总数）。 在这些网格中，有多少个属于 $S$？ 由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

输入通过标准输入给出，格式如下： > $N$ $M$ > $X_{1,1}\ X_{1,2}\ \dots\ X_{1,M}$ > $X_{2,1}\ X_{2,2}\ \dots\ X_{2,M}$ > $\vdots$ > $X_{N,1}\ X_{N,2}\ \dots\ X_{N,M}$

请输出一个整数，表示答案。

## 限制条件 - $N, M$ 为整数 - $1 \le N, M \le 18$ - $X$ 是由 `0`、`1`、`?` 组成的 $N$ 行 $M$ 列的网格 ## 样例解释 1 满足条件的网格共有如下 $6$ 个： ``` 011 011 001 010 011 110 001 011 011 111 110 111 ``` ## 样例解释 2 即使 $X$ 中没有 `?`，答案也有可能为 $0$。 ## 样例解释 3 请注意，答案需要对 $998244353$ 取模。 由 ChatGPT 4.1 翻译