ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4828: Little Artem and Graph

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

G. Little Artem and Graph
time limit per test
12 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
Input
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≤aij<i it is connected to. It is guaranteed that those vertices form a k-clique.
Output
Output a single integer− the number of spanning trees in the given graph modulo 109+7.
Examples
Input 
3 2
1 2
Output 
3
Input 
4 3
1 2 3
Output 
16

输入样例 复制

输出样例 复制

分类标签