Topology
给定一棵有 n 个节点、以节点 1 为根的树。保证每个节点的编号都小于它所有子节点的编号。
这棵树的一个拓扑序是节点 1,2,…,n 的一个排列 p1,p2,…,pn,满足每个父节点都出现在它的子节点之前。等价地,对于任意 1≤i<j≤n,节点 pj 都不是节点 pi 的父节点。
对于每个 1≤i≤n,求这棵树有多少个拓扑序满足 pi=i。答案对 998244353 取模。
这里的 pi=i 指整个拓扑序的第 i 个位置恰好放节点 i,不是在某棵子树内的位置。
输入格式
每个输入文件只有一组测试数据。
第一行一个整数 n,满足 2≤n≤5000,表示树的节点数。
第二行 n−1 个整数 f2,f3,…,fn,其中 1≤fi<i,表示节点 i 的父节点是 fi。
输出格式
输出一行 n 个由空格分隔的整数 a1,a2,…,an,其中 ai 是满足 pi=i 的拓扑序个数,对 998244353 取模。
样例 1
输入:
4
1 1 2
输出:
3 2 1 2
这棵树的全部拓扑序是 (1,2,3,4)、(1,3,2,4) 和 (1,2,4,3)。其中有 3 个满足 p1=1,2 个满足 p2=2,1 个满足 p3=3,2 个满足 p4=4。
样例 2
输入:
9
1 1 2 2 3 3 4 5
输出:
672 420 180 160 152 108 120 170 210