题目描述

给定一棵由 $n$ 个节点组成的树，其中节点 $1$ 是根。保证每个节点的编号都比它所有子节点小。树的拓扑序是一个满足以下限制的 $n$ 的排列 $p_1,p_2,\dots,p_n$：对于所有 $1\leq i<j\leq n$，节点 $p_j$ 都不是节点 $p_i$ 的父节点。

对于每个 $1 \le i \le n$，计算给定的树有多少拓扑序满足 $p_i=i$。答案对 $998\,244\,353$ 取模。

输入格式

每个测试文件仅有一组测试数据。

第一行输入一个整数 $n$（$2\leq n\leq 5\,000$），表示树的节点数量。

第二行输入 $(n-1)$ 个整数 $f_2,f_3,\dots,f_n$（$1\leq f_i< i$），其中 $f_i$ 是节点 $i$ 的父节点。

输出格式

输出一行 $n$ 个由单个空格分隔的整数 $a_1, a_2, \cdots, a_n$，其中 $a_i$ 表示给定的树有多少拓扑序满足 $p_i=i$。答案对 $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

提示

对于第一组样例数据，树的拓扑序有：$\{1, 2, 3, 4\}$, $\{1, 3, 2, 4\}$ 和 $\{1, 2, 4, 3\}$。其中有 $3$ 个序列满足 $p_1 = 1$，$2$ 个序列满足 $p_2 = 2$，$1$ 个序列满足 $p_3 = 3$, 以及 $2$ 个序列满足 $p_4 = 4$。