题目描述

我们有一个 $N$ 行和 $M$ 列的网格 $A$。初始时，每个方格上都写有 $0$。
让我们执行以下操作。

• 对于每个满足 $1 \leq i \leq N$ 的整数 $i$，在第 $i$ 行，将最左边的一个或多个方格中的数字变为 $1$。
• 对于每个满足 $1 \leq j \leq M$ 的整数 $j$，在第 $j$ 列，将最上方的一个或多个方格中的数字变为 $1$。

定义集合 $S$ 为所有可以通过这种方式得到的网格。

给定一个 $N$ 行 $M$ 列的网格 $X$，其中每个方格上的数字为 0、1 或 ?。
将每个 ? 替换为 0 或 1，可以得到 $2^q$ 个网格，其中 $q$ 是 $X$ 中 ? 的数量。有多少个这样的网格在集合 $S$ 中？
由于计算结果可能非常大，因此对 $998244353$ 取模。

约束条件

• $N$ 和 $M$ 是整数。
• $1 \leq N, M \leq 18$
• $X$ 是一个 $N$ 行 $M$ 列的网格，其中的数字为 0、1 或 ?。

输入

输入以以下格式从标准输入给出：

$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}$

输出

打印一个整数表示答案。

示例输入 1

2 3
0?1
?1?

示例输出 1

6

以下六个网格在 $S$ 中。

011  011  001
010  011  110

001  011  011
111  110  111

示例输入 2

5 3
101
010
101
010
101

示例输出 2

0

$X$ 中可能没有 ?，并且答案可能为 $0$。

示例输入 3

18 18
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????

示例输出 3

462237431

请确保对 $998244353$ 取模。