有一个包含 $$$r$$$ 行和 $$$c$$$ 列的网格,其中第 $$$i$$$ 行和 $$$j$$$ 列的正方形上写有一个整数 $$$a_{i, j}$$$。最初,所有元素都设置为 $$$0$$$。我们可以进行以下操作:
- 选择索引 $$$1 \le i \le r$$$ 和 $$$1 \le j \le c$$$,然后将同一行或同一列上的所有值替换为 $$$(i, j)$$$ 与值 xor $$$1$$$。换句话说,对于所有 $$$a_{x, y}$$$(其中 $$$x=i$$$ 或 $$$y=j$$$ 或两者),将 $$$a_{x, y}$$$ 替换为 $$$a_{x, y}$$$ x 或 $$$1$$$。
您想通过执行有限次数的上述操作来形成网格$$$b$$$。但是,$$$b$$$ 的某些元素丢失并被替换为“?”反而。
让 $$$k$$$ 为 '?' 的数量人物。在所有 $$$2^k$$$ 填充网格 $$$b$$$ 的方法中,通过替换每个“?”用“0”或“1”,从填充$$$0$$$的网格开始,计算通过执行有限次上述操作可以形成的网格数。由于这个数字可能很大,因此输出它对 $$$998244353$$$ 取模。
输入
第一行包含两个整数 $$$r$$$ 和 $$$c$$$ ($$$1 \le r, c \le 2000$$$) — 分别是网格的行数和列数。
接下来的 $$$r$$$ 行中的第 $$$i$$$ 行包含 $$$c$$$ 字符 $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$$$ ($$$b_{i, j} \in \{0, 1, ?\}$$$)。
输出
打印一个整数,表示填充网格 $$$b$$$ 模 $$$998244353$$$ 的方式数。
示例
输入 #1
3 3 ?10 1?? 010
输出 #1
1
输入 #2
2 3 000 001
输出 #2
0
输入 #3
1 1 ?
输出 #3
2
输入#4
6 9 1101011?0 001101?00 101000110 001011010 0101?01?? 00?1000?0
输出#4
8
注意
在第一个测试用例中,填写 $$$\texttt{?}$$$s 的唯一方法是这样填写:
010111010
这可以通过选择 $$$(i,j)=(2,2)$$$ 执行单个操作来完成。
在第二个测试用例中,可以表明没有可以生成该网格的操作序列。