Little Artem and Graph

Description:

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⁹ + 7.

Sample Input:

3 2
1 2

Sample Output:

3

Sample Input:

4 3
1 2 3

Sample Output:

16