24643번 - First to Solve 다국어

문제

The famous Forcedeltas Programming Contest features $n$ contestants, $m$ problems, and lasts for $k$ minutes.

For each contestant $i$ and each problem $j,ドル an integer $a_{i, j}$ is known. If $a_{i, j} = 0,ドル it means that contestant $i$ can not solve problem $j$. Otherwise, it means that contestant $i$ can solve problem $j$ in exactly $a_{i, j}$ minutes.

All contestants will follow the same strategy. Specifically, each contestant will form a list of all problems they can solve, shuffle the list uniformly at random, and solve the problems in that order, until the list ends or the contest is over.

For example, if the list for contestant $i$ looks like $j_1, j_2, \ldots$ after shuffling, then they will solve problem $j_1$ at minute $a_{i, j_1},ドル problem $j_2$ at minute $a_{i, j_1} + a_{i, j_2},ドル and so on. Note that no problem can be solved at minute $k + 1$ or later.

We'll say that contestant $i$ gets the First to Solve award for problem $j$ if no other contestant solves problem $j$ strictly earlier. In particular, it means that multiple contestants can get the award for the same problem.

Find the expected number of awards each contestant will get, modulo 998ドル,244円,353円$ (see the Output section for details).

입력

The first line contains three integers $n,ドル $m,ドル and $k$ --- the number of contestants, the number of problems, and the length of the contest in minutes (1ドル \le n \le 500$; 1ドル \le m \le 26$; 1ドル \le k \le 300$).

The $i$-th of the following $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ (0ドル \le a_{i, j} \le k$). The $j$-th of these integers denotes the number of minutes required for contestant $i$ to solve problem $j,ドル or 0ドル$ if contestant $i$ can not solve problem $j$.

출력

Print $n$ integers --- the expected number of awards contestants 1,ドル 2, \ldots, n$ will get, modulo 998ドル,244円,353円$.

Formally, let $M = 998,244円,353円$. It can be shown that the expected number of awards can be expressed as an irreducible fraction $\frac{p}{q},ドル where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Print the integer equal to $p \cdot q^{-1} \bmod M$. In other words, print such an integer $x$ that 0ドル \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

제한

힌트

In the example test, contestant 1ドル$ will always get the award for problem 1ドル,ドル contestant 2ドル$ will always get the award for problem 2ドル,ドル the expected number of awards contestant 3ドル$ will get is $\frac{3}{4},ドル contestant 4ドル$ will never get any awards, and the expected number of awards contestant 5ドル$ will get is $\frac{1}{2}$.