#P17886. Apple Tree

Apple Tree

给定一棵以 11 为根、含 nn 个结点的树。它满足:每个非根结点的直接孩子数量严格小于其父结点的直接孩子数量。

一个方案是二元组 (v,S)(v,S),其中 vv 为树上的结点,SS 是不含 vv 的、大小为 k−1k-1 的结点集合,并且存在整数 dd,使所有 u∈Su\in S 都满足 dist⁡(v,u)=d\operatorname{dist}(v,u)=d。距离定义为简单路径上的边数。

求方案数,答案对 998244353998244353 取模。不同中心或不同集合算不同方案。k=1k=1 时每个中心对应一个空集方案。

输入格式

第一行是测试用例数 tt,1≤t≤1041\le t\le10^4。

每组第一行两个整数 n,kn,k,2≤n≤5×1052\le n\le5\times10^5,1≤k≤n1\le k\le n。

第二行包含 p2,p3,…,pnp_2,p_3,\ldots,p_n,其中 1≤pi<i1\le p_i<i,表示结点 ii 的父亲。输入保证满足上述孩子数严格递减的条件。

所有测试用例的 nn 之和不超过 5×1055\times10^5。

输出格式

每组输出一个整数,表示方案数模 998244353998244353。

样例

3
3 3
1 1
5 2
1 1 2 3
6 3
1 1 1 2 2
1
20
16

第一组只有中心为 11、集合为 {2,3}\{2,3\} 的方案。