得分：$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 < i$ 和 $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)$。

现在，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$，在自己的行中打印答案。

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