配点 : $1000$ 点

問題文

ButCoder株式会社 は、プログラミングコンテストサイト「ButCoder」の開発や運営を主な事業とするスタートアップ企業です。

ButCoder社には社長を含めて $N$ 人の社員が在籍し、社長以外の各社員は直属の上司を一人だけ持ちます。各社員には $1$ から $N$ までの重複しない社員番号が割り当てられており、社員番号 $i$ の社員は社員 $i$ と呼ばれます。社長は社員 $1$ であり、社員 $i$ $(2 \leq i \leq N)$ の直属の上司は社員 $b_i$ $(1 \leq b_i < i)$ です。

ButCoder社員一同の集合写真を撮影するべく、全社員がButCoder本社の大広間に集まりました。この大広間はとても広く、$N$ 人全員が横一列に並ぶことができます。しかし、彼らはどのような順番で並ぶかを決めかねています。どういうわけか、彼らは社長以外みな、自分の直属の上司と隣り合って並ぶことを避けたいようです。

$N$ 人の社員の並び方であって、彼らの希望を満たすものは何通り存在するでしょうか？その個数を $10^9+7$ で割ったあまりを求めてください。

制約

• $2 \leq N \leq 2000$
• $1 \leq b_i < i$ $(2 \leq i \leq N)$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$b_2$

$b_3$

$:$

$b_N$

出力

$N$ 人の社員の並び方であって、社長を除くどの社員も自分の直属の上司と隣り合わないようなものの個数を $10^9+7$ で割ったあまりを出力せよ。

4
1
2
3

2

以下、社員 $A$ が社員 $B$ の直属の上司であることを $A \to B$ と表記します。

このケースでは、社員の主従関係は $1 \to 2 \to 3 \to 4$ となっています。以下の $2$ 通りの並び方が全社員の希望を満たします。

• $2, 4, 1, 3$
• $3, 1, 4, 2$

なお、後者は前者を左右に反転したものですが、これらは個別に数えます。

3
1
2

0

社員の主従関係は $1 \to 2 \to 3$ となっています。$3$ 人の社員がどのように並んでも、社員 $2$, $3$ の希望のうち少なくとも一方に反するため、答えは $0$ 通りです。

5
1
1
3
3

8

社員の主従関係は次の図のようになっています。

以下の $8$ 通りの並び方が全社員の希望を満たします。

• $1, 4, 5, 2, 3$
• $1, 5, 4, 2, 3$
• $3, 2, 4, 1, 5$
• $3, 2, 4, 5, 1$
• $3, 2, 5, 1, 4$
• $3, 2, 5, 4, 1$
• $4, 1, 5, 2, 3$
• $5, 1, 4, 2, 3$

15
1
2
3
1
4
2
7
1
8
2
8
1
8
2

97193524