← 返回题目列表

Codeforces · 641/G

G. 小 Artem 和图表

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

Little Artem 得到了一张图,构造如下:从一些 k-clique 开始,然后逐个添加新顶点,将它们连接到形成 k-clique 的 k 个已存在的顶点。

Artem 想要计算该图中生成树的数量以 109 + 7 为模。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ min(n, 5)) - 分别是图的总大小和初始团的大小。

接下来的 n - k 行通过列出连接到的 k 个不同顶点索引 1 ≤ aij < i 来描述第 k + 1 个、第 k + 2 个、...、第 i 个、...、第 n 个顶点。保证这些顶点形成 k-clique。

输出

输出一个整数——给定图中生成树的数量模 109 + 7。

示例

输入 #1

3 2
1 2

输出 #1

3

输入 #2

4 3
1 2 3

输出 #2

16