E - Strange Relation Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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) です．

すぬけくんは今，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 項目の値を記録する． これらの値の総和を \bmod (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

Score : 1500 points

Problem Statement

For an integer sequence of length N, A=(A_1,A_2,\cdots,A_N), and an integer T, let f(A,T) defined as follows:

  • f(A, T) is the lexicographically greatest integer sequence x that satisfies all of the conditions below. Here, under the constraints in this problem, it can be proved that there always are sequences that satisfy the conditions and that the number of those sequences is finite. Thus, f(A, T) can always be defined.

    • x is a sequence of length N consisting of non-negative integers.
    • For each i (1 \leq i \leq N), let y_i be the number of indices j such that j<i and A_j+T \times x_j < A_i+T \times x_i. Then, y_i=x_i holds.

For example, assume that A=(6,5,1) and T=3. Then, the sequences x that satisfy the conditions are: (0,0,0), (0,0,2), and (0,1,0). Thus, the value of f(A, T) is the lexicographically maximum among them: (0,1,0).

Now, Snuke has N integer sequences B_1,B_2,\cdots,B_N and an integer T. Each of the sequences B_i (1 \leq i \leq N) is an integer sequence of length K.

He will create an integer sequence A of length N and compute f(A, T). The value of A_i will be chosen from B_{i,1},B_{i,2},\cdots,B_{i,K}. Here, if B_i contains the same value multiple times, we will distinguish those occurrences; that is, there are K^N ways to create A.

For every i (1 \leq i \leq N), solve the following problem:

  • For all K^N choices of A, we will compute f(A,T) and record the value of its i-th element. Find the sum of these values, modulo (10^9+7).

Constraints

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

Input

Input is given from Standard Input in the following format:

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}

Output

For every i, print the answer in its own line.

Sample Input 1

2 2 1
1 2
1 2

Sample Output 1

0
3
  • For A=(1,1): f(A,T)=(0,1)
  • For A=(1,2): f(A,T)=(0,1)
  • For A=(2,1): f(A,T)=(0,0)
  • For A=(2,2): f(A,T)=(0,1)

Thus, the answer is 0+0+0+0=0 for i=1 and 1+1+0+1=3 for i=2.

Sample Input 2

3 2 3
6 2
5 3
1 4

Sample Output 2

0
6
13

Sample Input 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

Sample Output 3

0
248044096
333666695
536381826
8787512
11659012
661959013
166067001
529828166
526544756