跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1314. Little Artem and Graph

  • ID: 1320
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 图论
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Little Artem and Graph

题目描述

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


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 808 题。保留原作者与原赛事署名。