Problem Statement

For an integer sequence of length $N$, $A=(A_1,A_2,\cdots,A_N)$, and an integer $T$, let $f(A,T)$ defined as follows:

• $f(A, T)$ is the lexicographically greatest integer sequence $x$ that satisfies all of the conditions below. Here, under the constraints in this problem, it can be proved that there always are sequences that satisfy the conditions and that the number of those sequences is finite. Thus, $f(A, T)$ can always be defined.
• $x$ is a sequence of length $N$ consisting of non-negative integers.
  • For each $i$ ($1 \leq i \leq N$), let $y_i$ be the number of indices $j$ such that $j<i$ and $A_j+T \times x_j < A_i+T \times x_i$. Then, $y_i=x_i$ holds.

For example, assume that $A=(6,5,1)$ and $T=3$. Then, the sequences $x$ that satisfy the conditions are: $(0,0,0)$, $(0,0,2)$, and $(0,1,0)$. Thus, the value of $f(A, T)$ is the lexicographically maximum among them: $(0,1,0)$.

Now, Snuke has $N$ integer sequences $B_1,B_2,\cdots,B_N$ and an integer $T$. Each of the sequences $B_i$ ($1 \leq i \leq N$) is an integer sequence of length $K$.

He will create an integer sequence $A$ of length $N$ and compute $f(A, T)$. The value of $A_i$ will be chosen from $B_{i,1},B_{i,2},\cdots,B_{i,K}$. Here, if $B_i$ contains the same value multiple times, we will distinguish those occurrences; that is, there are $K^N$ ways to create $A$.

For every $i$ ($1 \leq i \leq N$), solve the following problem:

• For all $K^N$ choices of $A$, we will compute $f(A,T)$ and record the value of its $i$-th element. Find the sum of these values, modulo $(10^9+7)$.

Constraints

• $1 \leq N \leq 50$
• $1 \leq K \leq 50$
• $1 \leq T \leq 10^7$
• $1 \leq B_{i,j} \leq 10^9$

Input

Input is given from Standard Input in the following format:

N K T
B_{1,1} B_{1,2} \cdots B_{1,K}
B_{2,1} B_{2,2} \cdots B_{2,K}
\vdots
B_{N,1} B_{N,2} \cdots B_{N,K}

Output

For every $i$, print the answer in its own line.