分数: 1600 点
问题陈述
Maroon 提出了以下问题:
Snuke 有一个整数序列 a 长度 N。 最初, a_i=0 对于每个 i (1 \leq i \leq N).
Snuke 将以任意顺序重复以下两个操作任意次数:
-
操作 1:替换 a_i 与 a_i+x,其中 i (1 \leq i \leq N)和 x (x=1 or x=-1)是他选择的整数。 执行一次该操作的成本为 1.
-
操作 2:替换 a_i 与 a_i+x 对于每个 i (l \leq i \leq r),其中 l, r (1 \leq l \leq r \leq N)和 x (x=1 or x=-1)是他选择的整数。 执行一次该操作的成本为 C.
给你一个整数序列 A 长度 N。 斯努克想要制作 a_i=A_i 对于每个 i。 找出实现其目标所需的最低总成本。
然而,在准备这个问题的过程中,发现了太多意想不到的解决方案,所以Maroon将问题改成了如下:
Snuke 有 N 整数序列 B_1,B_2,\cdots,B_N 和整数 C 和 K。 每个序列的长度 B_i (1 \leq i \leq N)是 K.
现在,他想要制作一个整数序列 A 长度 N 并找到上述问题的答案。 的价值 A_i 将从中选择 B_{i,1},B_{i,2},\cdots,B_{i,K}。 在这里,即使有重复的值 B_{i,1},B_{i,2},\cdots,B_{i,K},我们仍然区分这些值。 也就是说,有 K^N 制作方法 A.
求上述问题所有方法的答案总和 A,模数 (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