题目描述

给定一个长度为 $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)$。

现在，すぬけくん有 $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$ 取模。

输入格式

输入按以下格式从标准输入给出。

$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

输出

0
3

样例 2

输入

3 2 3
6 2
5 3
1 4

输出

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

输出

0
248044096
333666695
536381826
8787512
11659012
661959013
166067001
529828166
526544756

说明/提示

数据范围

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

样例解释 1

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

由 ChatGPT 4.1 翻译