G. Меленький Артёмка и граф
ограничение по времени на тест
12 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У маленького Артёмки есть граф, который формируется следующим образом: начинаем с клики размера k, а затем добавляем новые вершины по одной, соединяя каждую новую вершину с k из уже существующих вершин, которые формируют k-клику.

Артёмка хочет узнать количество остовных деревьев в этом графе. Помогите ему вычислить эту величину по модулю 109 + 7.

Входные данные

В первой строке входных данных записаны два целых числа n и k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ min(n, 5)) — количество вершин в графе и размер исходной клики.

Следующие n - k строк определяют вершины графа с номерами k + 1, k + 2, ..., i, ..., n, для каждой из них описание состоит из k различных индексов вершин 1 ≤ aij < i, с которыми текущая вершина соединяется рёбрами при добавлении. Гарантируется, что эти вершины образуют k-клику.

Выходные данные

Выведите единственное целое число — количество остовных деревьев в данном графе по модулю 109 + 7.

Примеры
Входные данные
3 2
1 2
Выходные данные
3
Входные данные
4 3
1 2 3
Выходные данные
16