E - Increment Decrement 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 1600 点

問題文

maroon くんは以下のような問題を考えました．

すぬけ君は長さ N の整数列 a を持っています． 最初，すべての i (1 \leq i \leq N) について，a_i=0 です．

すぬけ君は，次の 2 つの操作を好きな順序で好きな回数繰り返します．

  • 操作 1: 好きな整数 i (1 \leq i \leq N) と x (x=1 or x=-1) を選び，a_i を a_i+x で置き換える． この操作は，1 回につき 1 のコストがかかる．

  • 操作 2: 好きな整数 l,r (1 \leq l \leq r \leq N) と x (x=1 or x=-1) を選び，すべての i (l \leq i \leq r) について，a_i を a_i+x で置き換える． この操作は，1 回につき C のコストがかかる．

長さ N の整数列 A が与えられます． すぬけくんの目標は，すべての i について，a_i=A_i とすることです． 目標を達成するために必要なコストの総和の最小値を求めてください．

しかし，この問題を準備していたところ，想定していない解法がたくさん見つかってしまいました． そこで，以下のように問題を変形しました．

すぬけくんは今，N 個の整数列 B_1,B_2,\cdots,B_N と，整数 C,K を持っています． B_i (1 \leq i \leq N) はすべて長さ K の整数列です．

これからすぬけくんは，長さ N の整数列 A を作り，上記の問題の答えを求めようとしています． A_i の値は，B_{i,1},B_{i,2},\cdots,B_{i,K} から選ぶことにします． ここで，B_i の値に重複があっても，それらの値を区別することにします． つまり，A の作り方は K^N 通り存在します．

すべての A に対する上記の問題の答えの総和を\bmod (10^9+7) で求めてください．

この問題を解いてください．

制約

  • 1 \leq N \leq 50
  • 1 \leq C \leq N
  • 1 \leq K \leq 50
  • 1 \leq B_{i,j} \leq 10^9
  • 入力はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．

N C K
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}

出力

答えを出力せよ．

入力例 1

5 2 1
2
3
1
2
1

出力例 1

6

A=(2,3,1,2,1) です． 最適な操作の一例を以下に示します．

  • l=1,r=5,x=1 として，操作 2 を実行する． a=(1,1,1,1,1) となる．
  • l=1,r=4,x=1 として，操作 2 を実行する． a=(2,2,2,2,1) となる．
  • i=2,x=1 として，操作 1 を実行する． a=(2,3,2,2,1) となる．
  • i=3,x=-1 として，操作 1 を実行する． a=(2,3,1,2,1) となる．

入力例 2

3 2 3
1 2 3
1 2 3
1 2 3

出力例 2

126

入力例 3

10 4 1
8
10
10
1
5
9
5
5
9
1

出力例 3

45

入力例 4

10 5 10
79 48 35 56 16 26 37 6 75 23
39 99 57 100 49 90 18 9 12 91
29 97 49 86 30 94 78 63 49 22
100 27 48 91 66 14 6 20 23 84
12 60 99 75 88 95 61 58 20 46
10 11 30 38 55 94 9 52 92 75
27 22 46 85 83 88 50 63 95 91
49 59 19 37 53 27 11 26 2 91
95 36 20 76 84 41 59 95 67 66
52 60 17 11 28 57 75 69 95 24

出力例 4

877826779

Score : 1600 points

Problem Statement

Maroon came up with the following problem:

Snuke has an integer sequence a of length N. Initially, a_i=0 for every i (1 \leq i \leq N).

Snuke will repeat the following two operations any number of times in any order:

  • Operation 1: Replace a_i with a_i+x, where i (1 \leq i \leq N) and x (x=1 or x=-1) are integers of his choice. The cost of doing this operation once is 1.

  • Operation 2: Replace a_i with a_i+x for every i (l \leq i \leq r), where l, r (1 \leq l \leq r \leq N) and x (x=1 or x=-1) are integers of his choice. The cost of doing this operation once is C.

You are given an integer sequence A of length N. Snuke wants to make a_i=A_i for every i. Find the minimum total cost needed to achieve his objective.

However, during the preparation of this problem, too many unexpected solutions were found, so Maroon changed the problem into the following:

Snuke has N integer sequences B_1,B_2,\cdots,B_N and integers C and K. The length of every sequence B_i (1 \leq i \leq N) is K.

Now, he wants to make an integer sequence A of length N and find the answer to the problem above. The value of A_i will be chosen from B_{i,1},B_{i,2},\cdots,B_{i,K}. Here, even if there are duplicated values in B_{i,1},B_{i,2},\cdots,B_{i,K}, we still distinguish those values. That is, there are K^N ways to make A.

Find the sum of the answers to the problem above over all the ways to make A, modulo (10^9+7).

Solve this problem.

Constraints

  • 1 \leq N \leq 50
  • 1 \leq C \leq N
  • 1 \leq K \leq 50
  • 1 \leq B_{i,j} \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C K
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

Print the answer.

Sample Input 1

5 2 1
2
3
1
2
1

Sample Output 1

6

We have A=(2,3,1,2,1). Below is one optimal sequence of operations:

  • Let l=1,r=5,x=1 and do Operation 2, resulting in a=(1,1,1,1,1).
  • Let l=1,r=4,x=1 and do Operation 2, resulting in a=(2,2,2,2,1).
  • Let i=2,x=1 and do Operation 1, resulting in a=(2,3,2,2,1).
  • Let i=3,x=-1 and do Operation 1, resulting in a=(2,3,1,2,1).

Sample Input 2

3 2 3
1 2 3
1 2 3
1 2 3

Sample Output 2

126

Sample Input 3

10 4 1
8
10
10
1
5
9
5
5
9
1

Sample Output 3

45

Sample Input 4

10 5 10
79 48 35 56 16 26 37 6 75 23
39 99 57 100 49 90 18 9 12 91
29 97 49 86 30 94 78 63 49 22
100 27 48 91 66 14 6 20 23 84
12 60 99 75 88 95 61 58 20 46
10 11 30 38 55 94 9 52 92 75
27 22 46 85 83 88 50 63 95 91
49 59 19 37 53 27 11 26 2 91
95 36 20 76 84 41 59 95 67 66
52 60 17 11 28 57 75 69 95 24

Sample Output 4

877826779