Олимпиадный тренинг

Задача . G. Меленький Артёмка и граф


Задача

Темы: *2300

У маленького Артёмки есть граф, который формируется следующим образом: начинаем с клики размера 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.


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

time 12000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w642
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет