A6731. 「NOI2023」桂花树

小 B 八年前看到的桂花树是一棵 $n$ 个节点的树 $T$，**保证 $T$ 的非根结点的父亲的编号小于自己**。给定整数 $k$，称一棵 $(n+m)$ 个节点的有根树 $T^{\prime}$ 是繁荣的，当且仅当以下所有条件满足：

1. 对于任意满足 $1 \le i,j \le n$ 的 $(i,j)$，在树 $T$ 和树 $T^{\prime}$ 上，节点 $i$ 和 $j$ 的最近公共祖先编号相同。
2. 对于任意满足 $1 \le i,j \le n + m$ 的 $(i,j)$，在树 $T^{\prime}$ 上，节点 $i$ 和 $j$ 的最近公共祖先编号不超过 $\max(i,j)+k$。

**注意题目中所有树的节点均从 $1$ 开始编号，且根结点编号为 $1$。$T^{\prime}$ 不需要满足非根结点的父亲编号小于自己。**

小 B 想知道有多少棵 $(n+m)$ 个节点的树是繁荣的，认为两棵树不同当且仅当存在某一个节点在两棵树上的父亲不同。你只输出方案数在模 $(10^9+7)$ 意义下的值。

从文件 tree.in 中读入数据。

**本题有多组测试数据。**

输入的第一行包含两个整数 $c,t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含三个整数 $n,m,k$。

输入的第二行包含 $n-1$ 个整数 $f_2,f_2,\dots,f_n$，其中 $f_i$ 表示 $T$ 中节点 $i$ 的父亲节点编号。

输出到文件 tree.out 中。

对于每组测试数据输出一行一个整数，表示繁荣的树的数量在模 $(10^9+7)$ 意义下的答案。

对于所有测试数据保证：$1 \le t \le 15$，$1 \le n \le 3 \times 10^4$，$0 \le m \le 3000$，$0 \le k \le 10$，$1 \le f_i \le i - 1$。

| 测试点编号 | $n \le$ | $m \le $| $k \le $|
| :--: | :--: | :--: | :--: |
| $1,2$ |$ 4$|$4$|$10$|
|$3$|$3\times 10^4$|$0$|$10$|
|$4$|$10^2$|$1$|$10$|
|$5$|$3 \times 10^4$|$1$|$10$|
|$6$|$10^2$|$2$|$10$|
|$7$|$3\times 10^4$|$2$|$10$|
|$8,9$|$1$|$10^2$|$0$|
|$10$|$1$|$3,000$|$0$|
|$11$|$1$|$10^2$|$10$|
|$12$|$1$|$3,000$|$10$|
|$13,14$|$ 10^2$|$10^2$|$0$|
|$15,16$|$3\times 10^4$|$3,000$|$0$|
|$17,18$|$ 10^2$|$10^2$|$10$|
|$19,20$|$3\times 10^4$|$3,000$|$10$|