Задача №113776. Лес
Рассмотрим следующую игру об удалении вершин из графа, представляющего лес (то есть объединение нескольких деревьев). Изначально граф состоит из одного дерева из n вершин, а количество очков равно 0 .
Игра задаётся перестановкой вершин и происходит следующим образом:
- Если граф опустел, то игра заканчивается.
- Иначе выбирается первая ещё не удалённая вершина в перестановке, после чего
- Количество очков увеличивается на размер дерева из которого была выбрана вершина, а затем выбранная вершина и все связанные с ней рёбра удаляются, и тот же процесс продолжается на оставшемся графе.
Просуммируем число очков по всем возможным n ! играм. Выведите это число по модулю 10 9 + 7 .
В первой строке входного файла дано число N ( 2 ≤ n ≤ 10 5 ) — количество вершин в исходном дереве.
Каждая из последующих N - 1 строк содержит два числа — x i , y i задающих концы соответствующего ребра дерева ( 1 ≤ x i , y i ≤ n ).
Выведите одно число — суммарное количество очков по модулю 10 9 + 7 .
Тесты к данной задаче состоят из 3 групп:
- (20 баллов) n ≤ 10 .
- (40 баллов) n ≤ 5000
- (40 баллов) n ≤ 10 5
2 1 2
6
3 1 2 2 3
34