G. Крестовый ксор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана таблица с $$$r$$$ строк и $$$c$$$ столбцов, где в клетке на пересечении $$$i$$$-й строки и $$$j$$$-го столбца записано целое число $$$a_{i, j}$$$. Изначально все элементы равны $$$0$$$. Мы можем выполнять следующую операцию:

  • Выберем индексы $$$1 \le i \le r$$$ и $$$1 \le j \le c$$$, затем заменим все значения в той же строке или столбце, что и $$$(i, j)$$$, значением xor $$$1$$$. Другими словами, для всех $$$a_{x, y}$$$, где хотя бы одно из $$$x=i$$$ и $$$y=j$$$ верно, мы заменим $$$a_{x, y}$$$ на $$$a_{x, y}$$$ xor $$$1$$$.

Вы хотите получить таблицу $$$b$$$, проделав вышеописанные операции конечное число раз. Однако, некоторые элементы $$$b$$$ отсутствуют и заменены на '?'.

Пусть $$$k$$$  — количество символов '?'. Среди всех $$$2^k$$$ способов заполнения таблицы $$$b$$$ путем замены каждого '?' на '0' или '1', подсчитайте количество таблиц, которые могут быть получены путем выполнения этой операции конечное число раз, начиная с таблицы, заполненной $$$0$$$. Поскольку это число может быть большим, выведите его по модулю $$$998244353$$$.

Входные данные

Первая строка содержит два целых числа $$$r$$$ и $$$c$$$ ($$$1 \le r, c \le 2000$$$)  — количество строк и столбцов таблицы соответственно.

$$$i$$$-я из следующих $$$r$$$ строк содержит $$$c$$$ символов $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$$$ ($$$b_{i, j} \in \{0, 1, ?\}$$$).

Выходные данные

Выведите одно целое число, представляющее количество способов заполнения таблицы $$$b$$$ по модулю $$$998244353$$$.

Примеры
Входные данные
3 3
?10
1??
010
Выходные данные
1
Входные данные
2 3
000
001
Выходные данные
0
Входные данные
1 1
?
Выходные данные
2
Входные данные
6 9
1101011?0
001101?00
101000110
001011010
0101?01??
00?1000?0
Выходные данные
8
Примечание

В первом примере единственный способ заполнить $$$\texttt{?}$$$  — это заполнить так:

010
111
010

Этого можно добиться, выполнив одну операцию, выбрав $$$(i,j)=(2,2)$$$.

Во втором примере можно показать, что не существует последовательности операций, которые могут создать такую таблицу.