← 返回题目列表

AtCoder · cf17_exhibition_a

A. 尴尬

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

ButCoder 公司。 是一家创业公司,主营业务为编程竞赛网站的开发和运营”但是编码器".

有 N 公司成员包括总裁,且除总裁外的每个成员都有一位直接上司。每个会员都有一个唯一的ID号 1 to N,以及具有 ID 的会员 i 称为会员 i。主席是会员 1,以及会员的直接老板 i (2 ≤ i ≤ N) 是会员 b_i (1 ≤ b_i < i).

ButCoder全体成员齐聚总公司大厅合影留念。大厅很大,而且都 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, 4, 1, 3
  • 3, 1, 4, 2

注意,后者与前者相反,但我们单独计数。


示例输入 2

3
1
2

示例输出 2

0

成员的层次结构是 1 → 2 → 3。无论排在什么顺序,至少有一个会员的愿望 2 和 3 不满意,所以答案是 0.


示例输入 3

5
1
1
3
3

示例输出 3

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