{"raw_statement":[{"iden":"statement","content":"Allen, having graduated from the MOO Institute of Techcowlogy (MIT), has started a startup! Allen is the president of his startup. He also hires $n-1$ other employees, each of which is assigned a direct superior. If $u$ is a superior of $v$ and $v$ is a superior of $w$ then also $u$ is a superior of $w$. Additionally, there are no $u$ and $v$ such that $u$ is the superior of $v$ and $v$ is the superior of $u$. Allen himself has no superior. Allen is employee number $1$, and the others are employee numbers $2$ through $n$.\n\nFinally, Allen must assign salaries to each employee in the company including himself. Due to budget constraints, each employee's salary is an integer between $1$ and $D$. Additionally, no employee can make strictly more than his superior.\n\nHelp Allen find the number of ways to assign salaries. As this number may be large, output it modulo $10^9 + 7$."},{"iden":"input","content":"The first line of the input contains two integers $n$ and $D$ ($1 \\le n \\le 3000$, $1 \\le D \\le 10^9$).\n\nThe remaining $n-1$ lines each contain a single positive integer, where the $i$\\-th line contains the integer $p_i$ ($1 \\le p_i \\le i$). $p_i$ denotes the direct superior of employee $i+1$."},{"iden":"output","content":"Output a single integer: the number of ways to assign salaries modulo $10^9 + 7$."},{"iden":"examples","content":"Input\n\n3 2\n1\n1\n\nOutput\n\n5\n\nInput\n\n3 3\n1\n2\n\nOutput\n\n10\n\nInput\n\n2 5\n1\n\nOutput\n\n15"},{"iden":"note","content":"In the first sample case, employee 2 and 3 report directly to Allen. The three salaries, in order, can be $(1,1,1)$, $(2,1,1)$, $(2,1,2)$, $(2,2,1)$ or $(2,2,2)$.\n\nIn the second sample case, employee 2 reports to Allen and employee 3 reports to employee 2. In order, the possible salaries are $(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)$."}],"translated_statement":[{"iden":"statement","content":"Allen 刚从 MOO 技术研究所（MIT）毕业，创办了一家初创公司！Allen 是他公司的总裁。他还雇佣了 $n -1$ 名其他员工，每人被分配一个直接上级。如果 $u$ 是 $v$ 的上级，且 $v$ 是 $w$ 的上级，则 $u$ 也是 $w$ 的上级。此外，不存在 $u$ 和 $v$ 使得 $u$ 是 $v$ 的上级且 $v$ 是 $u$ 的上级。Allen 本人没有上级。Allen 是员工编号 1，其余员工编号为 2 到 $n$。\n\n最后，Allen 必须为公司中的每位员工（包括他自己）分配薪水。由于预算限制，每位员工的薪水是一个介于 $1$ 和 $D$ 之间的整数。此外，任何员工的薪水都不能严格高于其直接上级。\n\n请帮助 Allen 计算分配薪水的方案数。由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。\n\n输入的第一行包含两个整数 $n$ 和 $D$（$1 lt.eq n lt.eq 3000$，$1 lt.eq D lt.eq 10^9$）。\n\n接下来的 $n -1$ 行，每行包含一个正整数，其中第 $i$ 行包含整数 $p_i$（$1 lt.eq p_i lt.eq i$）。$p_i$ 表示员工 $i + 1$ 的直接上级。\n\n请输出一个整数：分配薪水的方案数对 $10^9 + 7$ 取模的结果。\n\n在第一个样例中，员工 2 和 3 直接向 Allen 汇报。三个薪水（按顺序）可以是 $(1, 1, 1)$、$(2, 1, 1)$、$(2, 1, 2)$、$(2, 2, 1)$ 或 $(2, 2, 2)$。\n\n在第二个样例中，员工 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)$。"},{"iden":"input","content":"输入的第一行包含两个整数 $n$ 和 $D$（$1 lt.eq n lt.eq 3000$，$1 lt.eq D lt.eq 10^9$）。接下来的 $n -1$ 行，每行包含一个正整数，其中第 $i$ 行包含整数 $p_i$（$1 lt.eq p_i lt.eq i$）。$p_i$ 表示员工 $i + 1$ 的直接上级。"},{"iden":"output","content":"请输出一个整数：分配薪水的方案数对 $10^9 + 7$ 取模的结果。"},{"iden":"examples","content":"输入：\n3 2\n1\n1\n输出：\n5\n\n输入：\n3 3\n1\n2\n输出：\n10\n\n输入：\n2 5\n1\n输出：\n15"},{"iden":"note","content":"在第一个样例中，员工 2 和 3 直接向 Allen 汇报。三个薪水（按顺序）可以是 $(1, 1, 1)$、$(2, 1, 1)$、$(2, 1, 2)$、$(2, 2, 1)$ 或 $(2, 2, 2)$。\n\n在第二个样例中，员工 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)$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of employees, and $ D \\in \\mathbb{Z}^+ $ the maximum salary.  \nLet $ T = (V, E) $ be a rooted tree with $ n $ nodes, where:  \n- Node $ 1 $ is the root (Allen).  \n- For each $ i \\in \\{2, \\dots, n\\} $, there is a directed edge from $ p_i $ to $ i $, where $ p_i \\in \\{1, \\dots, i-1\\} $ is the direct superior of employee $ i $.  \n\nLet $ s: V \\to \\{1, 2, \\dots, D\\} $ be a salary assignment function.  \n\n**Constraints**  \n1. For every edge $ (u, v) \\in E $ (i.e., $ u $ is the direct superior of $ v $), it holds that $ s(u) \\geq s(v) $.  \n2. $ s(v) \\in \\{1, 2, \\dots, D\\} $ for all $ v \\in V $.  \n\n**Objective**  \nCompute the number of valid salary assignments $ s $ satisfying the above constraints, modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}