Little Artem and Graph

题意翻译

给定一张 $n$ 个点的[弦图](https://en.wikipedia.org/wiki/Chordal_graph)和定值 $k$，已知其完美消除序列为 $n, n - 1, \cdots, 1$。 这张图有一些特殊性质： - $\{ 1, 2, \cdots, k \}$ 是一个团。 - 对于点 $k + 1 \leq v \leq n$，记 $v$ 的邻域为 $N(v)$，则 $\lvert N(v) \cap \{ 1, 2, \cdots, v - 1 \} \rvert = k$。 求生成树的数量对 $10^9 + 7$ 取模的值。保证 $n \leq 10^4, k \leq 5$。

题目描述

Little Artem is given a graph, constructed as follows: start with some $ k $ -clique, then add new vertices one by one, connecting them to $ k $ already existing vertices that form a $ k $ -clique. Artem wants to count the number of spanning trees in this graph modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

First line of the input contains two integers $ n $ and $ k $ ( $ 1<=n<=10000 $ , $ 1<=k<=min(n,5) $ ) — the total size of the graph and the size of the initial clique, respectively. Next $ n-k $ lines describe $ k+1 $ -th, $ k+2 $ -th, ..., $ i $ -th, ..., $ n $ -th vertices by listing $ k $ distinct vertex indices $ 1<=a_{ij}&lt;i $ it is connected to. It is guaranteed that those vertices form a k-clique.

输出格式

Output a single integer — the number of spanning trees in the given graph modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

3 2
1 2

输出样例 #1

3

输入样例 #2

4 3
1 2 3

输出样例 #2

16