AT_agc049_e [AGC049E] Increment Decrement

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 \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 翻译