F. Первый, кто решит
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известный конкурс программирования Forcedeltas включает $$$n$$$ участников, $$$m$$$ задач и длится $$$k$$$ минут.

Для каждого участника $$$i$$$ и каждой задачи $$$j$$$ известно целое число $$$a_{i, j}$$$. Если $$$a_{i, j} = 0$$$, это означает, что участник $$$i$$$ не может решить задачу $$$j$$$. В противном случае, это означает, что участник $$$i$$$ может решить задачу $$$j$$$ за ровно $$$a_{i, j}$$$ минут.

Все участники будут следовать одной стратегии. Конкретно, каждый участник составит список всех задач, которые он может решить, перемешает список равномерно случайным образом и будет решать задачи в том порядке, пока список не закончится или конкурс не закончится.

Например, если список для участника $$$i$$$ выглядит как $$$j_1, j_2, \ldots$$$ после перемешивания, то он решит задачу $$$j_1$$$ в минуту $$$a_{i, j_1}$$$, задачу $$$j_2$$$ в минуту $$$a_{i, j_1} + a_{i, j_2}$$$ и так далее. Обратите внимание, что ни одна задача не может быть решена в минуту $$$k + 1$$$ или позже.

Мы скажем, что участник $$$i$$$ получает награду Первый, кто решит за задачу $$$j$$$, если никакой другой участник не решит задачу $$$j$$$ строго раньше. В частности, это означает, что несколько участников могут получить награду за одну и ту же задачу.

Найдите ожидаемое количество наград, которое каждый участник получит, по модулю $$$998\,244\,353$$$ (см. раздел "Вывод" для подробностей).

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество участников, количество задач и длительность конкурса в минутах ($$$1 \le n \le 500$$$; $$$1 \le m \le 26$$$; $$$1 \le k \le 300$$$).

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le k$$$). $$$j$$$-е из этих чисел обозначает количество минут, необходимых участнику $$$i$$$ для решения задачи $$$j$$$, или $$$0$$$, если участник $$$i$$$ не может решить задачу $$$j$$$.

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

Выведите $$$n$$$ целых чисел — ожидаемое количество наград, которые получат участники $$$1, 2, \ldots, n$$$, по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ожидаемое количество наград можно выразить в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x \lt M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Пример
Входные данные
5 3 60
30 0 0
40 20 0
30 60 0
0 0 0
60 60 1
Выходные данные
1
1
249561089
0
499122177
Примечание

В тестовом примере участник $$$1$$$ всегда получает награду за задачу $$$1$$$, участник $$$2$$$ всегда получает награду за задачу $$$2$$$, ожидаемое количество наград, которое получит участник $$$3$$$, равно $$$\frac{3}{4}$$$, участник $$$4$$$ никогда не получает наград, и ожидаемое количество наград, которое получит участник $$$5$$$, равно $$$\frac{1}{2}$$$.