← 返回题目列表

AtCoder · yahoo_procon2019_qual_e

E. 奇数子矩形

中文机器翻译题面 查看原题

分数: 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