Дано корневое дерево из \(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
4500 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач