Cross Xor

1000ms

262144K

Description:

There is a grid with $$$r$$$ rows and $$$c$$$ columns, where the square on the $$$i$$$-th row and $$$j$$$-th column has an integer $$$a_{i, j}$$$ written on it. Initially, all elements are set to $$$0$$$. We are allowed to do the following operation:

Choose indices $$$1 \le i \le r$$$ and $$$1 \le j \le c$$$, then replace all values on the same row or column as $$$(i, j)$$$ with the value xor $$$1$$$. In other words, for all $$$a_{x, y}$$$ where $$$x=i$$$ or $$$y=j$$$ or both, replace $$$a_{x, y}$$$ with $$$a_{x, y}$$$ xor $$$1$$$.

You want to form grid $$$b$$$ by doing the above operations a finite number of times. However, some elements of $$$b$$$ are missing and are replaced with '?' instead.

Let $$$k$$$ be the number of '?' characters. Among all the $$$2^k$$$ ways of filling up the grid $$$b$$$ by replacing each '?' with '0' or '1', count the number of grids, that can be formed by doing the above operation a finite number of times, starting from the grid filled with $$$0$$$. As this number can be large, output it modulo $$$998244353$$$.

Input:

The first line contains two integers $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le 2000$$$) — the number of rows and columns of the grid respectively.

The $$$i$$$-th of the next $$$r$$$ lines contain $$$c$$$ characters $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$$$ ($$$b_{i, j} \in \{0, 1, ?\}$$$).

Output:

Print a single integer representing the number of ways to fill up grid $$$b$$$ modulo $$$998244353$$$.

Sample Input:

Sample Output:

Sample Input:

2 3
000
001

Sample Output:

Sample Input:

1 1
?

Sample Output:

Sample Input:

Sample Output:

Note:

In the first test case, the only way to fill in the $$$\texttt{?}$$$s is to fill it in as such:

0	1	0
1	1	1
0	1	0

This can be accomplished by doing a single operation by choosing $$$(i,j)=(2,2)$$$.

In the second test case, it can be shown that there is no sequence of operations that can produce that grid.

Informação

Provedor Codeforces

Código CF1672G