分数: 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 这样 j<i 和 A_j+T \times x_j < A_i+T \times x_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.
他将创建一个整数序列 A 长度 N 并计算 f(A, T)。 的价值 A_i 将从中选择 B_{i,1},B_{i,2},\cdots,B_{i,K}。 在这里,如果 B_i 多次包含相同的值,我们将区分这些出现的情况;也就是说,有 K^N 创建方法 A.
对于每个 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)
因此,答案是 0+0+0+0=0 为 i=1 和 1+1+0+1=3 为 i=2.
示例输入 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