Задача №114887. Упорядочивания
Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.
Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя \(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 | 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} |
В первом тесте из примера Кэрол может выписать две перестановки: \(\{1, 2, 3\}\) или \(\{1, 3, 2\}\).
Во втором тесте Кэрол может выписать три перестановки: \(\{2, 3, 1, 4\}\), \(\{2, 3, 4, 1\}\) или \(\{2, 4, 3, 1\}\).
3 1 2 1 3
2
4 2 3 3 1 2 4
3