Cây khung của k-cây

Một đồ thị vô hướng được xây dựng theo quy tắc sau:

• Ban đầu đồ thị là một clique (đồ thị đầy đủ) gồm $k$ đỉnh, đánh số $1,2,\dots ,k$.
• Sau đó lần lượt thêm các đỉnh $k+1,k+2,\dots ,n$. Khi thêm đỉnh $i$, ta chọn $k$ đỉnh đã có sao cho chúng đôi một kề nhau (tức là tạo thành một clique kích thước $k$), rồi nối $i$ với cả $k$ đỉnh đó.

Hãy đếm số cây khung của đồ thị thu được, lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• $n-k$ dòng tiếp theo mô tả các đỉnh $k+1,k+2,\dots ,n$ theo thứ tự. Dòng thứ $i$ chứa $k$ số nguyên phân biệt (không nhất thiết theo thứ tự tăng dần), là chỉ số của $k$ đỉnh mà đỉnh $k+i$ được nối tới; mọi chỉ số đều nhỏ hơn $k+i$. Dữ liệu đảm bảo $k$ đỉnh này đôi một kề nhau tại thời điểm đỉnh $k+i$ được thêm vào.

Khi $n=k$ thì không có dòng nào tiếp theo.

Dữ liệu ra

Một số nguyên duy nhất: số cây khung của đồ thị, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 10000$
• $1\le k\le min(n,5)$

Ví dụ