← 返回题目

题库练习 Little Artem and Graph

← 上一题下一题 →

A10327 | $Little Artem and Graph$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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}<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

输入 #2

4 3
1 2 3

输出 #2

C++ 编辑器

输入

输出