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 ai,j is known. If ai,j=0, it means that contestant i can not solve problem j. Otherwise, it means that contestant i can solve problem j in exactly ai,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 j1,j2,… after shuffling, then they will solve problem j1 at minute ai,j1, problem j2 at minute ai,j1+ai,j2, 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 998244353 (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≤n≤500; 1≤m≤26; 1≤k≤300).
The i-th of the following n lines contains m integers ai,1,ai,2,…,ai,m (0≤ai,j≤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,…,n will get, modulo 998244353.
Formally, let M=998244353. It can be shown that the expected number of awards can be expressed as an irreducible fraction qp, where p and q are integers and q≡0(modM). Print the integer equal to p⋅q−1modM. In other words, print such an integer x that 0≤x<M and x⋅q≡p(modM).
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 43, contestant 4 will never get any awards, and the expected number of awards contestant 5 will get is 21.