DFS Order Position Counts on a Rooted Tree

You are given a rooted tree with n vertices numbered from 1 to n where vertex 1 is the root. In a depth‑first search (DFS) starting at the root, the DFS order is defined as the order in which the vertices are first visited. When exploring a vertex’s children, they can be visited in an arbitrary order – so many different DFS orders are possible.

Professor Pang is interested in the following: for each vertex \(v\) and every position \(j\) (1 \(\le\) \(j\) \(\le\) \(n\)), how many DFS orders are there such that vertex \(v\) is the \(j\)th vertex visited? Two DFS orders are considered different if there is at least one vertex whose order of appearance is different. Since the answers can be huge, output them modulo \(998244353\).

The DFS procedure is given in the pseudo‑code below. (In the process, the DFS order is the list dfs_order, whose jth element is the vertex visited at step \(j\).)

Note that if a vertex has \(k\) children, there are \(k!\) ways to order the recursive calls, and hence the total number of DFS orders for the tree is \[ F(1)=\prod_{u=1}^{n}(\deg(u))!\] (where \(\deg(u)\) is the number of children of \(u\)).

Input Format: The first line contains a single integer n. The second line contains n − 1 integers, where the \(i\)th integer (for \(i\ge2\)) is the parent of vertex \(i\). It is guaranteed that vertex 1 is the root.

Output Format: Print n lines. The \(i\)th line should contain n space‐separated integers. The \(j\)th integer on the \(i\)th line is the number of DFS orders in which vertex \(i\) appears in the \(j\)th position, modulo \(998244353\). If there is no DFS order in which vertex \(i\) appears at that position, output 0 for that entry.

Explanation: Formally, for each vertex \(v\) and position \(j\) (\(1 \le v,j \le n\)), compute

[ ans(v,j)=#{\text{DFS orders} : dfs_order[j]=v} \mod 998244353. ]

You may assume that n is small enough (for example, \(n\le 15\)) so that a solution using dynamic programming over subsets of children is feasible.

inputFormat

The first line contains an integer n (the number of vertices). The second line contains n − 1 integers. For \(i=2,3,\dots,n\), the \(i\)th number is the parent of vertex \(i\) (guaranteed that vertex 1 is the root).

outputFormat

Output n lines, each line containing n space‐separated integers. The \(j\)th integer in the \(i\)th line is the number of DFS orders in which vertex \(i\) appears in the \(j\)th position, modulo 998244353.

sample

3
1 1

2 0 0
0 1 1
0 1 1