98007 - 桂花树

时间限制 1 秒 内存限制 128 MB

题目描述

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

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

输入

本题每个测试点有多组测试数据。
输入的第一行包含两个整数 $c,t$ ，分别表示测试点编号和测试数据组数。(编号无意义)

接下来依次输入 $t$ 组测试数据，对于每组测试数据：
输入的第一行包含三个整数 $n,m,k$ 。
输入的第二行包含 $n-1$ 个整数 $f_2$ , $f_3$ , $f_4$ ,..., $f_n$ ,分别表示树 $T$ 中节点 $i$ 的父亲节点编号。

对于所有测试数据保证：
$1\leqt\leq25，1\leqn\leq3\times10^4，0\leqm\leq3000，0\leqk\leq10，1\leqf_i\leqi-1。$

输出

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

样例

样例 1

输入

输出

3
16
15

样例 2

输入

0 5
97 0 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
94 1 10
1 1 3 1 5 2 6 7 9 6 8 10 13 11 11 12 14 14 18 17 18 20 20 21 25 25 26 28 26 29 29 29 29 30 34 33 33 37 39 36 37 39 39 44 42 46 45 48 47 49 47 52 52 51 53 56 56 57 55 56 57 62 59 61 65 63 66 68 65 69 71 71 71 71 72 75 76 74 75 80 79 81 80 81 83 83 86 88 87 90 87 88 89
81 1 10
1 1 2 2 3 3 4 4 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 41 44 20 17 68 54 13
95 2 9
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
88 2 0
1 1 2 4 4 6 6 8 9 9 11 9 11 12 12 12 16 14 18 19 18 19 23 24 25 23 27 28 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 1 23 7 36 23 3 1 27 61 20 26 38 27 19 27 62 47 37 7 9 74 29 46 73 49 15 84 70 53 11

输出

提示

*本题测试数据为模拟数据，和赛场测试数据不同,另外本题实际限时500ms,本平台内最低限时1s,为此20号测试数据的 $t=25$

对于样例1中的第一组测试数据，有三棵合法的树，其每个节点的的父亲构成的序列 $\lbrace f_2,f_3 \rbrace$ 分别为 $\lbrace 1,1 \rbrace$ 、 $\lbrace 3,1 \rbrace$ 、 $\lbrace 1,2 \rbrace$ 。注意这组测试数据的第二行为空行。
对于样例1中的第二组、第三组测试数据，共有 16 棵树满足第一个条件，其中只有父亲序列 $\lbrace f_2,f_3,f_4 \rbrace$ 为 $\lbrace 4,4,1\rbrace$ 的树在第三组测试数据中不满足第二个条件。

来源

NOI