Дано корневое дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\). Корень дерева — вершина под номером \(1\).
Необходимо раскрасить все вершины дерева в \(n\) цветов (также пронумерованных от \(1\) до \(n\)) так, чтобы в каждый цвет была покрашена ровно одна вершина. Пусть \(c_i\) — цвет вершины \(i\), а \(p_i\) — родитель вершины \(i\) в корневом дереве. Раскраска называется красивой, если не существует такого \(k\) (\(k > 1\)), что \(c_k = c_{p_k} - 1\), то есть не существует вершины, цвет которой меньше цвета ее родителя ровно на \(1\).
Посчитайте количество красивых раскрасок и выведите его по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество красивых раскрасок, взятое по модулю \(998244353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
3 2
4 2
2 5
|
42
|
|
2
|
5
1 2
2 3
3 4
4 5
|
53
|
|
3
|
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
|