Reminder: in case of any technical issues, you can use the lightweight website
m1.codeforces.com,
m2.codeforces.com,
m3.codeforces.com.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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: Oct/17/2019 05:02:51 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|