Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.
Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя $$$n$$$ помещений, пронумерованных от $$$1$$$ до $$$n$$$. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно $$$n - 1$$$ переход между помещениями. Иными словами, карта убежища представляет собой дерево.
Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут перемещаться роботы.
После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.
Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений $$$p_1 p_2 \ldots p_n$$$, для которой верно, что если роботы могут перемещаться по переходу от помещения $$$p_i$$$ к помещению $$$p_j$$$, то $$$i \lt 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 \lt j$$$.
Эта задача состоит из пяти подзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех предыдущих подзадач и все тесты из условия.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
| 1 | 16 | $$$n \le 7$$$ | {—} |
| 2 | 16 | $$$n \le 15$$$ | {1} |
| 3 | 32 | $$$n \le 80$$$ | {1, 2} |
| 4 | 21 | $$$n \le 400$$$ | {1, 2, 3} |
| 5 | 15 | $$$n \le 3\,000$$$ | {1, 2, 3, 4} |
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\}$$$.
