Перший, хто розв'язав#11137

Перший, хто розв'язав

5 секунд

512 мегабайтів

Дуже складна

Відоме змагання з програмування Forcedeltas має $n$ учасників, $m$ задач і триває $k$ хвилин.

Для кожного учасника $i$ і кожної задачі $j$ відоме ціле число $a_{i, j}$ a_{i, j}. Якщо $a_{i, j} = 0$ a_{i, j} = 0, це означає, що учасник $i$ не може розв'язати задачу $j$ . Інакше це означає, що учасник $i$ може розв'язати задачу $j$ рівно за $a_{i, j}$ a_{i, j} хвилин.

Усі учасники дотримуватимуться однієї стратегії. Зокрема, кожен учасник складе список усіх задач, які він може розв'язати, перемішає список рівномірно випадковим чином і розв'язуватиме задачі в такому порядку, поки список не закінчиться або змагання не завершиться.

Наприклад, якщо список для учасника $i$ після перемішування виглядає як $j_{1}, j_{2}, \dots$ j_1, j_2, \ldots, то він розв'яже задачу $j_{1}$ j_1 на хвилині $a_{i, j_{1}}$ a_{i, j_1}, задачу $j_{2}$ j_2 на хвилині $a_{i, j_{1}} + a_{i, j_{2}}$ a_{i, j_1} + a_{i, j_2} і так далі. Зверніть увагу, що жодна задача не може бути розв'язана на хвилині $k + 1$ k + 1 або пізніше.

Ми скажемо, що учасник $i$ отримує нагороду Перший, хто розв'язав для задачі $j$ , якщо жоден інший учасник не розв'язав задачу $j$ строго раніше. Зокрема, це означає, що кілька учасників можуть отримати нагороду за одну й ту ж задачу.

Знайдіть очікувану кількість нагород, які отримає кожен учасник, за модулем $998244353$ (див. розділ Вихідні дані для деталей).

Вхідні дані

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

Наступні $n$ строк містять по $m$ цілих чисел $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} ( $0 \leq a_{i, j} \leq k$ 0 \le a_{i, j} \le k). $j$ -те з цих чисел позначає кількість хвилин, необхідних учаснику $i$ для розв'язання задачі $j$ , або $0$ , якщо учасник $i$ не може розв'язати задачу $j$ .

Вихідні дані

Виведіть $n$ цілих чисел — очікувану кількість нагород, які отримають учасники $1, 2, \dots, n$ 1, 2, \ldots, n, за модулем $998244353$ .

Формально, нехай $M = 998244353$ M = 998\,244\,353. Можна показати, що очікувана кількість нагород може бути виражена як нескоротний дріб $\frac{p}{q}$ \frac{p}{q}, де $p$ і $q$ є цілими числами і $q \neq \equiv 0 (mod M)$ q \not \equiv 0 \pmod{M}. Виведіть ціле число, яке дорівнює $p \cdot q^{- 1} mod M$ p \cdot q^{-1} \bmod M. Іншими словами, виведіть таке ціле число $x$ , що $0 \leq x < M$ 0 \le x < M і $x \cdot q \equiv p (mod M)$ x \cdot q \equiv p \pmod{M}.

Приклади

Приклад 1

Примітка

У прикладі тесту учасник $1$ завжди отримає нагороду за задачу $1$ , учасник $2$ завжди отримає нагороду за задачу $2$ , очікувана кількість нагород, які отримає учасник $3$ , дорівнює $\frac{3}{4}$ \frac{3}{4}, учасник $4$ ніколи не отримає жодної нагороди, а очікувана кількість нагород, які отримає учасник $5$ , дорівнює $\frac{1}{2}$ \frac{1}{2}.