English · Original
Chinese · Translation
Formal · Original
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$.
Finally, 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.
Help Allen find the number of ways to assign salaries. As this number may be large, output it modulo $10^9 + 7$.
## Input
The first line of the input contains two integers $n$ and $D$ ($1 \le n \le 3000$, $1 \le D \le 10^9$).
The 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$.
## Output
Output a single integer: the number of ways to assign salaries modulo $10^9 + 7$.
[samples]
## Note
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)$.
In 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)$.
Allen 刚从 MOO 技术研究所（MIT）毕业，创办了一家初创公司！Allen 是他公司的总裁。他还雇佣了 $n -1$ 名其他员工，每人被分配一个直接上级。如果 $u$ 是 $v$ 的上级，且 $v$ 是 $w$ 的上级，则 $u$ 也是 $w$ 的上级。此外，不存在 $u$ 和 $v$ 使得 $u$ 是 $v$ 的上级且 $v$ 是 $u$ 的上级。Allen 本人没有上级。Allen 是员工编号 1，其余员工编号为 2 到 $n$。
最后，Allen 必须为公司中的每位员工（包括他自己）分配薪水。由于预算限制，每位员工的薪水是一个介于 $1$ 和 $D$ 之间的整数。此外，任何员工的薪水都不能严格高于其直接上级。
请帮助 Allen 计算分配薪水的方案数。由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。
输入的第一行包含两个整数 $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$ 的直接上级。
请输出一个整数：分配薪水的方案数对 $10^9 + 7$ 取模的结果。
在第一个样例中，员工 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)$。
## Input
输入的第一行包含两个整数 $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$ 的直接上级。
## Output
请输出一个整数：分配薪水的方案数对 $10^9 + 7$ 取模的结果。
[samples]
## Note
在第一个样例中，员工 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)$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of employees, and $ D \in \mathbb{Z}^+ $ the maximum salary.
Let $ T = (V, E) $ be a rooted tree with $ n $ nodes, where:
- Node $ 1 $ is the root (Allen).
- 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 $.
Let $ s: V \to \{1, 2, \dots, D\} $ be a salary assignment function.
**Constraints**
1. For every edge $ (u, v) \in E $ (i.e., $ u $ is the direct superior of $ v $), it holds that $ s(u) \geq s(v) $.
2. $ s(v) \in \{1, 2, \dots, D\} $ for all $ v \in V $.
**Objective**
Compute the number of valid salary assignments $ s $ satisfying the above constraints, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "F. Cowmpany Cowmpensation",
"description": {
"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 dire",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF995F"
},
"statements": [
{
"statement_type": "Markdown",
"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 dire...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Allen 刚从 MOO 技术研究所（MIT）毕业，创办了一家初创公司！Allen 是他公司的总裁。他还雇佣了 $n -1$ 名其他员工，每人被分配一个直接上级。如果 $u$ 是 $v$ 的上级，且 $v$ 是 $w$ 的上级，则 $u$ 也是 $w$ 的上级。此外，不存在 $u$ 和 $v$ 使得 $u$ 是 $v$ 的上级且 $v$ 是 $u$ 的上级。Allen 本人没有上级。Allen 是...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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...",
"is_translate": false,
"language": "Formal"
}
]
}