分数: 600 点
问题陈述
我们有一个网格 A 与 N 行和 M 列。最初,
每个方格上都写有 0 。
让我们执行以下操作。
- 对于每个整数 i 这样 1 \le i \le N,在 i-第行,将零个或多个最左边方格中的数字变成 1.
- 对于每个整数 j 这样 1 \le j \le M,在 j第列,将零个或多个最上面的方格中的数字转换为 1.
让 S 是可以通过这种方式获得的网格的集合。
给你一个网格 X 与 N 行和 M 列组成 0, 1,和 ?.
有 2^q 可以通过替换每个网格来获得 ? 与 0 or 1,其中 q 是数量 ? in X。其中有多少人在 S?
这个计数可能很大,所以求它的模 998244353.
约束
- N 和 M 是整数。
- 1 \le N,M \le 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.