题目描述

maroon くん想出了如下的问题。

---

すぬけ君有一个长度为 $N$ 的整数序列 $a$。最开始，对于所有 $i$（$1 \leq i \leq N$），都有 $a_i=0$。

すぬけ君可以按任意顺序、任意次数重复以下两种操作：

• 操作 $1$：选择任意整数 $i$（$1 \leq i \leq N$）和 $x$（$x=1$ 或 $x=-1$），将 $a_i$ 替换为 $a_i+x$。每执行一次该操作，花费 $1$ 的代价。
• 操作 $2$：选择任意整数 $l,r$（$1 \leq l \leq r \leq N$）和 $x$（$x=1$ 或 $x=-1$），对于所有 $i$（$l \leq i \leq r$），将 $a_i$ 替换为 $a_i+x$。每执行一次该操作，花费 $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$，上述问题的答案之和，并对 $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

输入

5 2 1
2
3
1
2
1

输出

6

样例 2

输入

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

输出

126

样例 3

输入

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

输出

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

输出

877826779

说明/提示

数据范围

• $1 \leq N \leq 50$
• $1 \leq C \leq N$
• $1 \leq K \leq 50$
• $1 \leq B_{i,j} \leq 10^9$
• 所有输入均为整数。

样例解释 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)$。

由 ChatGPT 4.1 翻译