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