Aleksei recibió un manzano de tamaño $n$ como regalo de cumpleaños. Como programador competitivo que es, decidió calcular el número de tartas de $k$ manzanas en el árbol.
Un manzano de tamaño $n$ se define como un árbol con raíz de $n$ vértices, con raíz en el vértice $1$, donde cada vértice tiene estrictamente menos hijos directos que su padre (excepto la raíz, que no tiene padre).
Una tarta de $k$ manzanas es un par $(v, S)$ donde:
- $v \in V$ es un vértice del árbol (el centro),
- $S \subset V \setminus \{v\}$ es un conjunto de vértices de tamaño $k - 1$,
- existe un entero $d$ tal que para todo $u \in S$, $\text{dist}(v, u) = d$.
La distancia $\text{dist}(u, v)$ se define como el número de aristas en el camino simple entre los vértices $u$ y $v$.
En otras palabras, una tarta de $k$ manzanas consta de un vértice $v$ (el centro) y otros $k - 1$ vértices que se encuentran todos a la misma distancia de $v$.
Tu tarea es calcular el número de tartas de $k$ manzanas en el árbol dado.
Como la respuesta puede ser muy grande, imprímela módulo $998\,244\,353$.
Entrada
Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 10^4$). A continuación sigue la descripción de los casos de prueba.
Cada caso de prueba comienza con una línea que contiene dos enteros $n$ y $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): el número de vértices en el manzano y el tamaño de la tarta de manzanas.
La siguiente línea contiene $n - 1$ enteros $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), donde $p_i$ denota el padre del vértice $i$ en el manzano.
La suma de $n$ en todos los casos de prueba no supera $5 \cdot 10^5$.
Salida
Para cada caso de prueba, imprime un único entero: el número de tartas de $k$ manzanas módulo $998\,244\,353$.
Ejemplos
Entrada 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Salida 1
1 20 16
Nota
En el primer caso de prueba, la única tarta existente tiene su centro en el vértice $1$, y el conjunto correspondiente es $S = \{2, 3\}$.