配点 : $1500$ 点

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$, および整数 $T$ に対して，$f(A,T)$ を，つぎのように定義します．

• $f(A,T)$ は，以下の条件をすべて満たす整数列 $x$ の中で，辞書順最大のものである． なおこの問題の制約下では，条件を満たす数列は必ず存在し，またその個数は有限であることが証明できる．よって，$f(A,T)$ は必ず定義できる．
  • $x$ は長さ $N$ の非負整数列である．
  • 各 $i$ ($1 \leq i \leq N$) について，$y_i$ を，$j かつ$A_j+T \times x_j < A_i+T \times x_i$を満たす$j$の個数，と定義する．このとき，$y_i=x_i$ である．
• $x$ は長さ $N$ の非負整数列である．
• 各 $i$ ($1 \leq i \leq N$) について，$y_i$ を，$j$ かつ $A_j+T \times x_j < A_i+T \times x_i$ を満たす $j$ の個数，と定義する．このとき，$y_i=x_i$ である．

例えば，$A=(6,5,1),T=3$ であるとします． この時，条件を満たす数列 $x$ として，$(0,0,0),(0,0,2),(0,1,0)$ が考えられます． よって，$f(A,T)$ の値は，この中で辞書順最大の $(0,1,0)$ です．

すぬけくんは今，$N$ 個の整数列 $B_1,B_2,\cdots,B_N$ と，整数 $T$ を持っています． $B_i$ ($1 \leq i \leq N$) はすべて長さ $K$ の整数列です．

これからすぬけくんは，長さ $N$ の整数列 $A$ を作り，$f(A,T)$ を求めようとしています． $A_i$ の値は，$B_{i,1},B_{i,2},\cdots,B_{i,K}$ から選ぶことにします． ここで，$B_i$ の値に重複があっても，それらの値を区別することにします． つまり，$A$ の作り方は $K^N$ 通り存在します．

すべての $i$ ($1 \leq i \leq N$) について，次の問題を解いてください．

• $K^N$ 通りすべての $A$ について $f(A,T)$ を求め，その $i$ 項目の値を記録する． これらの値の総和を $\bmod (10^9+7)$ で求めよ．

制約

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

入力

入力は以下の形式で標準入力から与えられる．

$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}$

出力

すべての $i$ について，答えを一行ごとに出力せよ．

2 2 1
1 2
1 2

0
3

• $A=(1,1)$ の場合: $f(A,T)=(0,1)$
• $A=(1,2)$ の場合: $f(A,T)=(0,1)$
• $A=(2,1)$ の場合: $f(A,T)=(0,0)$
• $A=(2,2)$ の場合: $f(A,T)=(0,1)$

よって，$i=1$ のときの答えは $0+0+0+0=0$ であり， $i=2$ のときの答えは $1+1+0+1=3$ です．

3 2 3
6 2
5 3
1 4

0
6
13

10 15 45
129 82 26 185 217 258 22 192 24 117 167 255 91 180 203
171 73 168 26 208 169 115 164 121 214 154 196 172 66 230
185 178 241 220 243 143 111 124 10 62 56 117 254 43 81
201 74 213 163 204 35 44 203 207 73 218 60 243 51 250
229 117 212 245 112 152 206 96 266 165 105 94 231 41 27
261 201 258 111 100 72 239 31 199 203 226 151 72 268 44
94 19 47 243 133 174 141 82 190 62 175 256 126 123 210
186 64 73 82 68 183 261 120 265 212 18 24 36 152 92
205 101 186 91 172 153 91 242 141 97 247 193 45 245 66
225 97 162 213 61 219 184 195 80 203 79 72 269 258 199

0
248044096
333666695
536381826
8787512
11659012
661959013
166067001
529828166
526544756