CF1672G.Cross Xor

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$.

有一个 $r$ 行 $c$ 列的网格，其中第 $i$ 行第 $j$ 列的方格上写有一个整数 $a_{i, j}$。初始时，所有元素均为 $0$。我们允许执行以下操作：

• 选择下标 $1 \le i \le r$ 和 $1 \le j \le c$，然后将所有与位置 $(i, j)$ 处于同一行或同一列的元素的值异或 $1$。换言之，对所有满足 $x=i$ 或 $y=j$（或两者同时成立）的 $a_{x, y}$，将其替换为 $a_{x, y} \oplus 1$。

你希望通过对上述操作执行有限次，得到目标网格 $b$。然而，$b$ 中部分元素缺失，被替换为字符 '?'。

设 $k$ 为 '?' 字符的个数。在所有 $2^k$ 种将每个 '?' 替换为 '0' 或 '1' 的填充方式中，统计有多少种填充后的网格 $b$ 可以通过从全零网格出发、执行上述操作有限次而得到。由于答案可能很大，请输出其对 $998244353$ 取模的结果。

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, ?}$).

第一行包含两个整数 $r$ 和 $c$（$1 \le r, c \le 2000$），分别表示网格的行数和列数。

接下来的 $r$ 行中，第 $i$ 行包含 $c$ 个字符 $b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$（其中 $b_{i, j} \in \{0, 1, ?\}$）。

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

输出一个整数，表示填充网格 $b$ 的方案数对 $998244353$ 取模的结果。

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.

在第一个测试用例中，填充 $\texttt{?}$ 的唯一方式如下所示：

0

1

0

1

1

1

0

1

0

这可以通过执行一次操作实现，即选择 $(i,j)=(2,2)$。

在第二个测试用例中，可以证明不存在任何操作序列能够生成该网格。