# Tree Coloring solution codeforces

You are given a rooted tree consisting of 𝑛n vertices numbered from 11 to 𝑛n. The root of the tree is the vertex 11.

You have to color all vertices of the tree into 𝑛n colors (also numbered from 11 to 𝑛n) so that there is exactly one vertex for each color. Let 𝑐𝑖ci be the color of vertex 𝑖i, and 𝑝𝑖pi be the parent of vertex 𝑖i in the rooted tree. The coloring is considered beautiful if there is no vertex 𝑘k (𝑘>1k>1) such that 𝑐𝑘=𝑐𝑝𝑘−1ck=cpk−1, i. e. no vertex such that its color is less than the color of its parent by exactly 11.

Calculate the number of beautiful colorings, and print it modulo 998244353998244353.

The first line contains one integer 𝑛n (2≤𝑛≤2500002≤n≤250000) — the number of vertices in the tree.

Then 𝑛−1n−1 lines follow, the 𝑖i-th line contains two integers 𝑥𝑖xi and 𝑦𝑖yi (1≤𝑥𝑖,𝑦𝑖≤𝑛1≤xi,yi≤n; 𝑥𝑖≠𝑦𝑖xi≠yi) denoting an edge between the vertex 𝑥𝑖xi and the vertex 𝑦𝑖yi. These edges form a tree.

Print one integer — the number of beautiful colorings, taken modulo 998244353998244353.

input v Tree Coloring solution codeforces

5 1 2 3 2 4 2 2 5

output

42

input

5 1 2 2 3 3 4 4 5

output

53

input

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

output

955085064