Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро
ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила
своего наставника Йон-Рогга.
Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту
убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого
помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра
не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными
словами, карта убежища представляет собой дерево.
Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения
этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут
перемещаться роботы.
После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует
ребра нарисованного дерева.
Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех
номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в
любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению,
которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров
помещений p1p2 . . . pn, для которой верно, что если роботы могут перемещаться по переходу от
помещения pi к помещению pj , то i < j.
Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют
условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим,
Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.
Формат входных данных
Первая строка входных данных содержит единственное целое число n — количество помещений
в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).
Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от
помещения a к помещению b.
Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно
добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном
направлению движения роботов в этом переходе).
Формат выходных данных
Выведите остаток от деления на 998 244 353 количества различных перестановок p1p2 . . . pn, для которых верно, что если роботы перемещаются по переходу от помещения pi к помещению pj , то
i < j.
|
Ввод |
Вывод |
|
3
1 2
1 3
|
2 |
|
4
2 3
3 1
2 4
|
3 |
Замечание
В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.
Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.