28848번 - Упорядочивания 다국어

Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.

Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя $n$ помещений, пронумерованных от $1$ до $n$. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно $n - 1$ переход между помещениями. Иными словами, карта убежища представляет собой дерево.

Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут перемещаться роботы.

После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.

Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений $p_1 p_2 \ldots p_n$, для которой верно, что если роботы могут перемещаться по переходу от помещения $p_i$ к помещению $p_j$, то $i < j$.

Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на $998\,244\,353$.

Первая строка входных данных содержит единственное целое число $n$ --- количество помещений в убежище, нарисованном Йон-Роггом ($1 \le n \le 3\,000$).

Каждая из следующих $n - 1$ строк содержит два целых числа $a$, $b$ --- номера помещений, соединенных очередным коридором ($1 \le a, b \le n$). Роботы перемещаются по коридору в направлении от помещения $a$ к помещению $b$.

Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).

Выведите остаток от деления на $998\,244\,353$ количества различных перестановок $p_1 p_2 \ldots p_n$, для которых верно, что если роботы перемещаются по переходу от помещения $p_i$ к помещению $p_j$, то $i < j$.

В первом тесте из примера Кэрол может выписать две перестановки: $\{1, 2, 3\}$ или $\{1, 3, 2\}$.

Во втором тесте Кэрол может выписать три перестановки: $\{2, 3, 1, 4\}$, $\{2, 3, 4, 1\}$ или $\{2, 4, 3, 1\}$.