atcoder#YAHOOPROCON2019QUALE. Odd Subrectangles

Odd Subrectangles

Score : 800800 points

Problem Statement

There is a square grid with NN rows and MM columns. Each square contains an integer: 00 or 11. The square at the ii-th row from the top and the jj-th column from the left contains aija_{ij}.

Among the 2N+M2^{N+M} possible pairs of a subset AA of the rows and a subset BB of the columns, find the number of the pairs that satisfy the following condition, modulo 998244353998244353:

  • The sum of the AB|A||B| numbers contained in the intersection of the rows belonging to AA and the columns belonging to BB, is odd.

Constraints

  • 1N,M3001 \leq N,M \leq 300
  • 0ai,j1(1iN,1jM)0 \leq a_{i,j} \leq 1(1\leq i\leq N,1\leq j\leq M)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN MM

a11a_{11} ...... a1Ma_{1M}

::

aN1a_{N1} ...... aNMa_{NM}

Output

Print the number of the pairs of a subset of the rows and a subset of the columns that satisfy the condition, modulo 998244353998244353.

2 2
0 1
1 0
6

For example, if AA consists of the first row and BB consists of both columns, the sum of the numbers contained in the intersection is 0+1=10+1=1.

2 3
0 0 0
0 1 0
8