F. Раскраска дерева
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано корневое дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Корень дерева — вершина под номером $$$1$$$.

Необходимо раскрасить все вершины дерева в $$$n$$$ цветов (также пронумерованных от $$$1$$$ до $$$n$$$) так, чтобы в каждый цвет была покрашена ровно одна вершина. Пусть $$$c_i$$$ — цвет вершины $$$i$$$, а $$$p_i$$$ — родитель вершины $$$i$$$ в корневом дереве. Раскраска называется красивой, если не существует такого $$$k$$$ ($$$k > 1$$$), что $$$c_k = c_{p_k} - 1$$$, то есть не существует вершины, цвет которой меньше цвета ее родителя ровно на $$$1$$$.

Посчитайте количество красивых раскрасок и выведите его по модулю $$$998244353$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 250000$$$) — количество вершин в дереве.

Затем следует $$$n-1$$$ строка, $$$i$$$-я из них содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), обозначающих ребро между вершинами $$$x_i$$$ и $$$y_i$$$. Эти ребра задают дерево.

Выходные данные

Выведите одно целое число — количество красивых раскрасок, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
5
1 2
3 2
4 2
2 5
Выходные данные
42
Входные данные
5
1 2
2 3
3 4
4 5
Выходные данные
53
Входные данные
20
20 19
20 4
12 4
5 8
1 2
20 7
3 10
7 18
11 8
9 10
17 10
1 15
11 16
14 11
18 10
10 1
14 2
13 17
20 6
Выходные данные
955085064