毕业于 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)$$$。