← 返回题目列表

AtCoder · agc049_e

E. 增量 减量

中文机器翻译题面 查看原题

分数: 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