Арыки яблоневого сада
В яблоневом саду на берегу Иссык-Куля 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 раз.
Комментарии