Дана таблица с \(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\).
Выходные данные
Выведите одно целое число, представляющее количество способов заполнения таблицы \(b\) по модулю \(998244353\).
Примечание
В первом примере единственный способ заполнить \(\texttt{?}\) — это заполнить так:
Этого можно добиться, выполнив одну операцию, выбрав \((i,j)=(2,2)\).
Во втором примере можно показать, что не существует последовательности операций, которые могут создать такую таблицу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
?10
1??
010
|
1
|
|
2
|
2 3
000
001
|
0
|
|
3
|
1 1
?
|
2
|
|
4
|
6 9
1101011?0
001101?00
101000110
001011010
0101?01??
00?1000?0
|
8
|