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

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

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

In the first test case, the only way to fill in the $ \texttt{?} $ s is to fill it in as such: 010111010This 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.