分数: 800 点
问题陈述
有一个正方形网格 N 行和 M 列。 每个方格包含一个整数: 0 or 1。广场位于 i从顶部开始的第行和 j左起第 列包含 a_{ij}.
其中 2^{N+M} 可能的子集对 A 行和子集 B 列中,找到满足以下条件的对的数量,取模 998244353:
- 总和 |A||B| 属于以下行的交集中包含的数字 A 以及属于的列 B是奇数。
约束
- 1 \leq N,M \leq 300
- 0 \leq a_{i,j} \leq 1(1\leq i\leq N,1\leq j\leq M)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
a_{11} ... a_{1M}
:
a_{N1} ... a_{NM}
输出
打印满足条件的行子集和列子集对的数量,模 998244353.
示例输入 1
2 2 0 1 1 0
示例输出 1
6
例如,如果 A 由第一行和 B 由两列组成,交集包含的数字之和为 0+1=1.
示例输入 2
2 3 0 0 0 0 1 0
示例输出 2
8