Арыки яблоневого сада


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В яблоневом саду на берегу Иссык-Куля n деревьев пронумерованы от 1 до n. Садовник Таалай соединяет их арыками: каждый арык идёт между двумя деревьями, и вода должна доходить от любого дерева до любого другого, причём арыков ровно n − 1 (то есть получается дерево в смысле теории графов).

У дерева номер 1 стоит насос, и к нему удобно подвести ровно d арыков. Кроме того, Таалай хочет, чтобы ровно c деревьев были «концевыми» — к ним подходит ровно один арык.

Рисунок

Для каждого из T вопросов n c d найдите количество способов провести арыки по модулю 10⁹ + 7. Способы различаются, если какой-то арык (пара деревьев) есть в одном способе и нет в другом.

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

В первой строке — число T (1 ≤ T ≤ 5). В каждой из следующих T строк — три целых числа n c d (2 ≤ n ≤ 10⁶, 1 ≤ c ≤ n, 1 ≤ d ≤ n − 1).

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

Для каждого вопроса выведите количество способов по модулю 10⁹ + 7.

Пример 1

Вход:

4
4 2 1
4 3 3
4 2 2
4 3 1

Выход:

6
1
6
3

Пояснение

При n = 4 деревьев с двумя концевыми вершинами (это пути) 12, а с тремя (это «звёзды») 4. Если к дереву 1 подходит ровно 3 арыка, то оно центр звезды: способ один. Путей, в которых дерево 1 — концевое, 6 (оно в начале пути, остальные три дерева идут в любом порядке).

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов n ≤ 8, ещё в 10 % тестов n ≤ 10⁵.

Подсказка

Код Прюфера: деревья на вершинах 1…n взаимно однозначно соответствуют последовательностям длины n − 2 из чисел от 1 до n; вершина степени k встречается в коде ровно k − 1 раз.


Комментарии

Еще нет ни одного комментария.