← 返回题目列表

Codeforces · 995/F

F. 牛仔补偿

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

毕业于 MOO 理工学院 (MIT) 的 Allen 已经开始创业了!艾伦是他的初创公司的总裁。他还雇佣了 $$$n-1$$$ 其他员工,每个员工都被指派了一名直接上级。如果 $$$u$$$ 是 $$$v$$$ 的上级,并且 $$$v$$$ 是 $$$w$$$ 的上级,那么 $$$u$$$ 也是 $$$w$$$ 的上级。此外,不存在 $$$u$$$ 和 $$$v$$$ 使得 $$$u$$$ 优于 $$$v$$$ 且 $$$v$$$ 优于 $$$u$$$。艾伦本人没有上级。 Allen 是员工编号 $$$1$$$,其他人是员工编号 $$$2$$$ 到 $$$n$$$。

最后,Allen 必须为公司中的每个员工(包括他自己)分配工资。由于预算限制,每个员工的工资是 $$$1$$$ 到 $$$D$$$ 之间的整数。此外,任何员工的收入都不能严格高于其上级。

帮助艾伦找出分配工资的方法数。由于这个数字可能很大,因此输出它对 $$$10^9 + 7$$$ 取模。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$D$$$ ($$$1 \le n \le 3000$$$, $$$1 \le D \le 10^9$$$)。

其余 $$$n-1$$$ 行每行包含一个正整数,其中第 $$$i$$$ 行包含整数 $$$p_i$$$ ($$$1 \le p_i \le i$$$)。 $$$p_i$$$ 表示员工$$$i+1$$$ 的直接上级。

输出

输出一个整数:以 $$$10^9 + 7$$$ 为模的工资分配方式的数量。

示例

输入 #1

3 2
1
1

输出 #1

5

输入 #2

3 3
1
2

输出 #2

10

输入 #3

2 5
1

输出 #3

15

注意

在第一个示例案例中,员工 2 和 3 直接向 Allen 报告。这三个工资按顺序可以是 $$$(1,1,1)$$$、$$$(2,1,1)$$$、$$$(2,1,2)$$$、$$$(2,2,1)$$$ 或 $$$(2,2,2)$$$。

在第二个示例案例中,员工 2 向 Allen 汇报,员工 3 向员工 2 汇报。按顺序,可能的工资为 $$$(1,1,1)$$$、$$$(2,1,1)$$$、$$$(2,2,1)$$$、$$$(2,2,2)$$$、$$$(3,1,1)$$$、 $$$(3,2,1)$$$、$$$(3,2,2)$$$、$$$(3,3,1)$$$、$$$(3,3,2)$$$、$$$(3,3,3)$$$。