P9479 [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)$ 意义下的值。

无

无

**【样例解释 #1】** 对于样例中的第一组测试数据，有三棵合法的树，其每个节点的的父亲构成的序列 $\{f_2,f_3\}$ 分别为 $\{1,1\}$、$\{3,1\}$、$\{1,2\}$。注意这组测试数据的第二行为空行。 对于样例中的第二组、第三组测试数据，共有 $16$ 棵树满足第一个条件，其中只有父亲序列为 $\{4,4,1\}$ 的树在第三组测试数据中不满足第二个条件。 **【样例解释 #2】** 该组样例满足 $n \le 100$，五组测试数据中 $m$ 分别不超过 $0, 1, 1, 2, 2$。 **【样例解释 #3】** 该组样例满足 $k = 0$，五组测试数据中前两组测试数据满足 $n = 1$，第一、三、四组测试数据满足 $n, m \le 100$。 **【样例解释 #4】** 该组样例前两组测试数据满足 $n = 1$，第一、三、四组测试数据满足 $n, m \le 100$。 **【数据范围】** 对于所有测试数据保证：$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$|