A - Awkward Editorial /

Time Limit: 3 sec / Memory Limit: 512 MB

配点 : 1000 点

問題文

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

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

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

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

制約

  • 2 ≤ N ≤ 2000
  • 1 ≤ b_i < i (2 ≤ i ≤ N)

入力

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

N
b_2
b_3
:
b_N

出力

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

入力例 1

4
1
2
3

出力例 1

2

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

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

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

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

入力例 2

3
1
2

出力例 2

0

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

入力例 3

5
1
1
3
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

入力例 4

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

出力例 4

97193524

Score : 1000 points

Problem Statement

ButCoder Inc. is a startup company whose main business is the development and operation of the programming competition site "ButCoder".

There are N members of the company including the president, and each member except the president has exactly one direct boss. Each member has a unique ID number from 1 to N, and the member with the ID i is called Member i. The president is Member 1, and the direct boss of Member i (2 ≤ i ≤ N) is Member b_i (1 ≤ b_i < i).

All the members in ButCoder have gathered in the great hall in the main office to take a group photo. The hall is very large, and all N people can stand in one line. However, they have been unable to decide the order in which they stand. For some reason, all of them except the president want to avoid standing next to their direct bosses.

How many ways are there for them to stand in a line that satisfy their desires? Find the count modulo 10^9+7.

Constraints

  • 2 ≤ N ≤ 2000
  • 1 ≤ b_i < i (2 ≤ i ≤ N)

Input

Input is given from Standard Input in the following format:

N
b_2
b_3
:
b_N

Output

Print the number of ways for the N members to stand in a line, such that no member except the president is next to his/her direct boss, modulo 10^9+7.

Sample Input 1

4
1
2
3

Sample Output 1

2

Below, we will write A → B to denote the fact that Member A is the direct boss of Member B.

In this case, the hierarchy of the members is 1 → 2 → 3 → 4. There are two ways for them to stand in a line that satisfy their desires:

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

Note that the latter is the reverse of the former, but we count them individually.

Sample Input 2

3
1
2

Sample Output 2

0

The hierarchy of the members is 1 → 2 → 3. No matter what order they stand in, at least one of the desires of Member 2 and 3 is not satisfied, so the answer is 0.

Sample Input 3

5
1
1
3
3

Sample Output 3

8

The hierarchy of the members is shown below:

There are eight ways for them to stand in a line that satisfy their desires:

  • 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

Sample Input 4

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

Sample Output 4

97193524