给你一棵有根树,由 $$$n$$$ 个顶点组成。树中的顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。设 $$$d_x$$$ 为从根到顶点 $$$x$$$ 的距离(最短路径上的边数)。
有一个芯片最初放置在根部。您可以根据需要多次执行以下操作(可能为零):
- 将筹码从当前顶点 $$$v$$$ 移动到顶点 $$$u$$$,使得 $$$d_u = d_v + 1$$$。如果$$$v$$$是根,则可以选择任何满足此约束的顶点$$$u$$$;但是,如果 $$$v$$$ 不是根,则 $$$u$$$ 不应该是 $$$v$$$ 的邻居(不应该有连接 $$$v$$$ 和 $$$u$$$ 的边)。
例如,在上面的树中,可以进行以下筹码移动:$$$1 \rightarrow 2$$$、$$$1 \rightarrow 5$$$、$$$2 \rightarrow 7$$$、$$$5 \rightarrow 3$$$、$$$5 \rightarrow 4$$$、$$$3 \rightarrow 6$$$、$$$7 \rightarrow 6$$$。
顶点序列是 有效 如果您可以按照序列中给出的顺序移动芯片,使其访问序列中的所有顶点(并且仅访问它们)。
您的任务是计算有效顶点序列的数量。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$)。
第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 顶点的父顶点。顶点 $$$1$$$ 是根。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 有效顶点序列的数量,以 $$$998244353$$$ 为模。
示例
输入复制
341 2 131 271 2 2 1 4 5
输出复制
4 2 8
注意
在第一个示例中,以下序列有效:$$$[1]$$$、$$$[1, 2]$$$、$$$[1, 4]$$$、$$$[1, 4, 3]$$$。
在第二个示例中,以下序列有效:$$$[1]$$$、$$$[1, 2]$$$。
在第三个示例中,以下序列有效: $$$[1]$$$、$$$[1, 2]$$$、$$$[1, 2, 7]$$$、$$$[1, 2, 7, 6]$$$、$$$[1, 5]$$$、$$$[1, 5, 3]$$$、$$$[1, 5, 3, 6]$$$, $$$[1, 5, 4]$$$。