问题描述

对于一个长度为$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$为满足$A_j+T \times x_j < A_i+T \times x_i$的下标$j$的个数，其中$j<i$。则有$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)$。

现在，Snuke有$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$个元素的值。求这些值的和，模$(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$，在单独的行中打印答案。

示例输入1

2 2 1
1 2
1 2

示例输出1

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

示例输入2

3 2 3
6 2
5 3
1 4

示例输出2

0
6
13

示例输入3

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

示例输出3

0
248044096
333666695
536381826
8787512
11659012
661959013
166067001
529828166
526544756