#2025. 「NOI 2023」桂花树

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

1. 对于任意满足 的 ，在树 和树 上，节点 和 的最近公共祖先编号相同。
2. 对于任意满足 的 ，在树 上，节点 和 的最近公共祖先编号不超过 。

注意题目中所有树的节点均从 开始编号，且根结点编号为 。 不需要满足非根结点的父亲编号小于自己。

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

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

本题有多组测试数据。

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

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

输入的第一行包含三个整数 。

输入的第二行包含 个整数 ，其中 表示 中节点 的父亲节点编号。

输出到文件 tree.out 中。

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

样例 1 输入

0 3
1 2 1

2 2 1
1
2 2 0
1

样例 1 输出

3
16
15

样例 1 解释

对于样例中的第一组测试数据，有三棵合法的树，其每个节点的的父亲构成的序列 分别为 、、。注意这组测试数据的第二行为空行。

对于样例中的第二组、第三组测试数据，共有 棵树满足第一个条件，其中只有父亲序列为 的树在第三组测试数据中不满足第二个条件。

样例 2

见附件中的 tree/tree2.in 与 tree/tree2.ans。

该组样例满足 ，五组测试数据中 分别不超过 。

样例 3

见附件中的 tree/tree3.in 与 tree/tree3.ans。

该组样例满足 ，五组测试数据中前两组测试数据满足 ，第一、三、四组测试数据满足 。

样例 4

见附件中的 tree/tree4.in 与 tree/tree4.ans。

该组样例前两组测试数据满足 ，第一、三、四组测试数据满足 。

对于所有测试数据保证：，，，，。