题目描述

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)$ で求めてください．

---

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

输入格式

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

$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. 选定一项使其 $+1$ 或者 $-1$ , 会花费 $1$ 的代价.
2. 选定一个区间使区间中的每一项 $+1$ 或者 $-1$ , 会花费 $C$ 的代价.

定义一个非负整数序列的代价为从全 $0$ 序列变为该序列所需的最小代价.

给定 $n$ 个序列 $B_i$ , 每个序列长为 $K$ , 依次将每个 $A_i$ 赋值为 $B_{i,1},B_{i,2},\dots,B_{i,K}$ , 求所有 $K^n$ 个可能的 $A$ 序列代价和.

5 2 1
2
3
1
2
1

6

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

提示

制約

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

Sample Explanation 1

$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)$ となる．