AT_agc048_e.[AGC048E] Strange Relation

给定一个长度为 $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 \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 翻译