Description

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<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 Format

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< i$), where $f_i$ is the parent of vertex $i$.

Output Format

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$.

4
1 1 2

3 2 1 2

9
1 1 2 2 3 3 4 5

672 420 180 160 152 108 120 170 210

Hint

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$.