配点 : $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}$

出力

答えを出力せよ．

5 2 1
2
3
1
2
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)$ となる．

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

126

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

45

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

877826779