Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Little Artem and Graph

time limit per test

12 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLittle 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.

Input

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.

Output

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

Examples

Input

3 2

1 2

Output

3

Input

4 3

1 2 3

Output

16

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/19/2019 09:49:41 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|