题目描述

著名的 Forcedeltas Programming Contest 有 $n$ 名参赛者、$m$ 道题，比赛持续 $k$ 分钟。

对于每名参赛者 $i$ 和每道题 $j$，给定一个整数 $a_{i,j}$：

• 如果 $a_{i,j}=0$，表示参赛者 $i$ 无法解决题目 $j$；
• 否则，表示参赛者 $i$ 恰好需要 $a_{i,j}$ 分钟解决题目 $j$。

所有参赛者都会采用同一种策略：

1. 把自己能够解决的所有题组成一个列表；
2. 对这个列表进行等概率随机排列；
3. 按排列后的顺序依次做题，直到列表结束，或者比赛时间耗尽。

例如，若参赛者 $i$ 随机排列后的题目顺序为

$$j_1,j_2,\ldots,$$

那么他会在第 $a_{i,j_1}$ 分钟解决 $j_1$，在第

$$a_{i,j_1}+a_{i,j_2}$$

分钟解决 $j_2$，以此类推。

注意：在第 $k+1$ 分钟及以后完成的题目不算作比赛期间解出。

如果对于某道题 $j$，不存在其他参赛者比参赛者 $i$ 严格更早解出它，那么称参赛者 $i$ 获得题目 $j$ 的 First to Solve（首解）奖。

因此，如果若干名参赛者在同一时刻最早解出同一道题，他们都可以获得该题的首解奖。

请计算每名参赛者获得首解奖数量的期望值，并对 $998244353$ 取模。

输入格式

第一行包含三个整数 $n,m,k$：

• $n$：参赛者数量；
• $m$：题目数量；
• $k$：比赛持续时间（分钟）。

满足

$$1\le n\le 500,\qquad 1\le m\le 26,\qquad 1\le k\le 300.$$

接下来 $n$ 行，第 $i$ 行包含 $m$ 个整数

$$a_{i,1},a_{i,2},\ldots,a_{i,m},$$

其中

$$0\le a_{i,j}\le k.$$

$a_{i,j}=0$ 表示参赛者 $i$ 无法解决题目 $j$；否则表示其解题所需时间。

输出格式

输出 $n$ 个整数，依次表示参赛者 $1,2,\ldots,n$ 获得首解奖数量的期望值，对 $998244353$ 取模后的结果。

形式化地，设

$$M=998244353.$$

若某个期望值写成最简分数 $\frac pq$，且

$$q\not\equiv 0\pmod M,$$

则应输出

$$p\cdot q^{-1}\bmod M.$$

也就是说，输出唯一的 $x$，满足

$$0\le x<M,\qquad xq\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$ 获得首解奖数量的期望为 $\frac34$；
• 参赛者 $4$ 不会获得任何首解奖；
• 参赛者 $5$ 获得首解奖数量的期望为 $\frac12$。