CF641G.Little Artem and Graph

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 109 + 7.

小 Artem 得到了一个按如下方式构造的图：首先从某个 $k$-团（即包含 $k$ 个顶点的完全子图）出发，然后逐个添加新顶点，每次添加一个新顶点时，将其与图中已存在的、构成一个 $k$-团的 $k$ 个顶点全部相连。

Artem 想要求出该图的生成树个数，并对 $10^9 + 7$ 取模。

First line of the input contains two integers n and k (1 ≤ n ≤ 10 000, 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 < i it is connected to. It is guaranteed that those vertices form a k-clique.

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10\,000$，$1 \leq k \leq \min(n,\,5)$），分别表示图的总大小以及初始团（clique）的大小。

接下来的 $n - k$ 行依次描述第 $k+1$ 个、第 $k+2$ 个、……、第 $i$ 个、……、第 $n$ 个顶点：每行列出 $k$ 个互不相同的顶点编号 $1 \leq a_{ij} < i$，表示该顶点与这些编号的顶点相连。保证这些顶点构成一个 $k$-团。

Output a single integer — the number of spanning trees in the given graph modulo 109 + 7.

输出一个整数——给定图的生成树数量对 $10^9 + 7$ 取模的结果。