C. Topology
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$n$$$ vertices, rooted at vertex $$$1$$$. It is guaranteed that every vertex has a smaller index than all of its children. A topological order of this tree is a permutation $$$p_1,p_2,\dots,p_n$$$ of $$$n$$$ that satisfies the following constraint: For all $$$1\leq i \lt j\leq n$$$, vertex $$$p_j$$$ is not the parent of vertex $$$p_i$$$.

For each $$$1 \le i \le n$$$, calculate the number of topological orders of the given tree satisfying $$$p_i=i$$$, modulo $$$998\,244\,353$$$.

Input

There is only one test case in each test file.

The first line contains an integer $$$n$$$ ($$$2\leq n\leq 5\,000$$$), denoting the number of vertices of the tree.

The second line contains $$$(n-1)$$$ integers $$$f_2,f_3,\dots,f_n$$$ ($$$1\leq f_i \lt i$$$), where $$$f_i$$$ is the parent of vertex $$$i$$$.

Output

Output one line containing $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ separated by a space, where $$$a_i$$$ is the number of topological orders satisfying $$$p_i=i$$$, modulo $$$998\,244\,353$$$.

Examples
Input
4
1 1 2
Output
3 2 1 2
Input
9
1 1 2 2 3 3 4 5
Output
672 420 180 160 152 108 120 170 210
Note

For the first sample test case, all topological orders of the tree are $$$\{1, 2, 3, 4\}$$$, $$$\{1, 3, 2, 4\}$$$ and $$$\{1, 2, 4, 3\}$$$. There are $$$3$$$ of them satisfying $$$p_1 = 1$$$, $$$2$$$ of them satisfying $$$p_2 = 2$$$, $$$1$$$ of them satisfying $$$p_3 = 3$$$, and $$$2$$$ of them satisfying $$$p_4 = 4$$$.