/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
1 から N の番号がついた N 頂点の有向木が与えられます。
頂点 1 はこの木の根です。 2 \leq i \leq N を満たす整数 i について、頂点 p_i から i へ向かう有向辺が存在します。
a を (1,\ldots,N) を並び替えて得られる数列とします。また、a の i 番目の項を a_i とします。
a としてありうる数列は N! 通りあります。それらのうち、下記の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。
- 条件：1 \leq i \leq N を満たす任意の整数 i について、頂点 a_i から 1 度以上辺を辿って頂点 i へ到達することはできない。
制約
- 与えられる入力は全て整数
- 1 \leq N \leq 2000
- 1 \leq p_i < i
入力
入力は以下の形式で標準入力から与えられる。
N
p_{2} \cdots p_N
出力
(1,\ldots,N) の並び替え a のうち、問題文中の条件を満たすものの個数を 998244353 で割ったあまりを出力せよ。
入力例 1
4 1 1 3
出力例 1
4
入力例 2
30 1 1 3 1 5 1 1 1 8 9 7 3 11 11 15 14 4 10 11 12 1 10 13 11 7 23 8 12 18
出力例 2
746746186
- 998244353 で割ったあまりを出力するのを忘れずに。
Score : 700 points
Problem Statement
Given is a directed tree with N vertices numbered 1 through N.
Vertex 1 is the root of the tree. For each integer i such that 2 \leq i \leq N, there is a directed edge from Vertex p_i to i.
Let a be the permutation of (1, \ldots, N), and a_i be the i-th element of a.
Among the N! sequences that can be a, find the number of sequences that satisfy the following condition, modulo 998244353.
- Condition: For every integer i such that 1 \leq i \leq N, Vertex i is unreachable from Vertex a_i by traversing one or more edges.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2000
- 1 \leq p_i < i
Input
Input is given from Standard Input in the following format:
N
p_{2} \cdots p_N
Output
Print the number of sequences a among the permutations of (1, \ldots, N) that satisfy the condition in Problem Statement, modulo 998244353.
Sample Input 1
4 1 1 3
Sample Output 1
4
Sample Input 2
30 1 1 3 1 5 1 1 1 8 9 7 3 11 11 15 14 4 10 11 12 1 10 13 11 7 23 8 12 18
Sample Output 2
746746186
- Remember to print the count modulo 998244353.