Problem Description

The osmanthus tree that Little B saw eight years ago was a tree $T$ with $n$ nodes. It is guaranteed that, for every non-root node in $T$, the index of its parent is smaller than its own index. Given an integer $k$, a rooted tree $T^{\prime}$ with $(n+m)$ nodes is called prosperous if and only if all the following conditions are satisfied:

1. For any pair $(i,j)$ with $1 \le i,j \le n$, in both tree $T$ and tree $T^{\prime}$, the index of the lowest common ancestor of nodes $i$ and $j$ is the same.
2. For any pair $(i,j)$ with $1 \le i,j \le n + m$, in tree $T^{\prime}$, the index of the lowest common ancestor of nodes $i$ and $j$ is at most $\max(i,j)+k$.

Note that all trees in this problem are indexed starting from $1$, and the root has index $1$. $T^{\prime}$ does not need to satisfy that the parent index of a non-root node is smaller than its own.

Little B wants to know how many prosperous trees with $(n+m)$ nodes there are. Two trees are considered different if and only if there exists some node whose parent is different in the two trees. You only need to output the number of valid trees modulo $(10^9+7)$.

Input Format

This problem has multiple test cases.

The first line contains two integers $c,t$, representing the test point ID and the number of test cases. $c=0$ means this test point is the sample.

Then each test case is given as follows:

The first line contains three integers $n,m,k$.

The second line contains $n-1$ integers $f_2,f_3,\dots,f_n$, where $f_i$ is the index of the parent of node $i$ in $T$.

Output Format

For each test case, output one integer per line, the number of prosperous trees modulo $(10^9+7)$.

0 3
1 2 1

2 2 1
1
2 2 0
1

3
16
15

见附件中的 tree/tree2.in。

见附件中的 tree/tree2.ans。

见附件中的 tree/tree3.in。

见附件中的 tree/tree3.ans。

见附件中的 tree/tree4.in。

见附件中的 tree/tree4.ans。

Hint

[Sample Explanation #1]

For the first test case in the sample, there are three valid trees. The sequence of parents of each node, $\{f_2,f_3\}$, is respectively $\{1,1\}$, $\{3,1\}$, and $\{1,2\}$. Note that the second line of this test case is an empty line.

For the second and third test cases in the sample, there are $16$ trees that satisfy the first condition, and among them only the tree with parent sequence $\{4,4,1\}$ does not satisfy the second condition in the third test case.

[Sample Explanation #2]

This sample group satisfies $n \le 100$. In the five test cases, $m$ is at most $0, 1, 1, 2, 2$, respectively.

[Sample Explanation #3]

This sample group satisfies $k = 0$. In the five test cases, the first two test cases satisfy $n = 1$, and the first, third, and fourth test cases satisfy $n, m \le 100$.

[Sample Explanation #4]

In this sample group, the first two test cases satisfy $n = 1$, and the first, third, and fourth test cases satisfy $n, m \le 100$.

[Constraints]

For all testdata, it is guaranteed that $1 \le t \le 15$, $1 \le n \le 3 \times 10^4$, $0 \le m \le 3000$, $0 \le k \le 10$, and $1 \le f_i \le i - 1$.

Translated by ChatGPT 5