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

В Японии есть огромное число традиционных способов приготовить одни и те же ингредиенты. Будем считать, что всего есть $$$n$$$ различных способов приготовления, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ традиционных ингредиентов, пронумерованных от $$$1$$$ до $$$m$$$.

Известный шеф-повар устраивает мастер-класс и собирается приготовить ровно $$$a_{i, j}$$$ блюд, используя $$$i$$$-й способ готовки и $$$j$$$-й ингредиент как основной. Соответственно, суммарное число приготовленных блюд будет равно $$$A = \sum\limits_{i=1}^n \sum\limits_{j=1}^m a_{i, j}$$$.

Два известных кулинарных критика планируют посетить мастер-класс, и шеф-повар заранее планирует, какие $$$k$$$ из этих $$$A$$$ блюд он предоставит им на дегустацию. Разумеется, у критиков есть строгие правила, которые они выдвигают к выбранному набору блюд:

  • набор должен быть непустой; то есть хотя бы одно блюдо должно быть подано, $$$k \ge 1$$$;
  • все блюда в наборе должны быть приготовлены попарно различными способами;
  • не более половины поданных блюд должны быть приготовлены с использованием одного и того же ингредиента в качестве основного; иными словами, для любого ингредиента число блюд с ним в основе должно не превосходить $$$\left\lfloor\frac{k}{2}\right\rfloor$$$.

Шефа интересует, сколько есть различных способов выбрать набор произвольного размера из множества $$$A$$$ возможных блюд, который удовлетворит критиков? Наборы считаются различными, если есть хотя бы одно блюдо, присутствующее в одном из них, но не в другом. Поскольку это число может быть большим, найдите остаток от его деления на $$$998\,244\,353$$$.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — число способов приготовления и число традиционных ингредиентов ($$$1 \le n \le 100$$$; $$$1 \le m \le 2000$$$).

В $$$i$$$-й из следующих $$$n$$$ строк перечислены $$$m$$$ целых чисел $$$a_{i, j}$$$ — число возможных блюд с использованием $$$i$$$-го способа приготовления и $$$j$$$-го ингредиента ($$$0 \le a_{i,j} \le 998\,244\,353$$$).

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

Выведите единственное число — остаток от деления числа удовлетворяющих критиков наборов блюд на $$$998\,244\,353$$$.

Система оценки

Баллы за подзадачи начисляются только в случае, если все тесты соответствующей подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы$$$n = $$$$$$m = $$$$$$a_{i,j} \lt $$$ Необходимые подзадачи Информация о проверке
0–примеры из условияполная
14$$$2$$$$$$2$$$$$$2$$$первая ошибка
24$$$2$$$$$$3$$$$$$2$$$1первая ошибка
34$$$5$$$$$$2$$$$$$2$$$1первая ошибка
44$$$5$$$$$$3$$$$$$2$$$1 – 3первая ошибка
54$$$10$$$$$$2$$$$$$2$$$1, 3первая ошибка
64$$$10$$$$$$3$$$$$$2$$$1 – 5первая ошибка
74$$$10$$$$$$2$$$$$$1000$$$1, 3, 5первая ошибка
84$$$10$$$$$$3$$$$$$1000$$$1 – 7первая ошибка
916$$$40$$$$$$2$$$$$$1000$$$1, 3, 5, 7первая ошибка
1016$$$40$$$$$$3$$$$$$1000$$$1 – 9первая ошибка
1120$$$40$$$$$$500$$$$$$1000$$$0 – 10первая ошибка
1216$$$100$$$$$$2000$$$$$$998\,244\,353$$$0 – 11первая ошибка
Примеры
Входные данные
2 3
1 0 1
0 1 1
Выходные данные
3
Входные данные
3 3
1 2 3
4 5 0
6 0 0
Выходные данные
190
Входные данные
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1
0 1 1 0 1
Выходные данные
742