Aleksei a reçu un pommier de taille $n$ comme cadeau d'anniversaire. Étant lui-même adepte de programmation compétitive, il a décidé de calculer le nombre de tartes à $k$ pommes dans l'arbre.
Un pommier de taille $n$ est défini comme un arbre enraciné à $n$ sommets, dont la racine est le sommet $1$, où chaque sommet possède strictement moins d'enfants directs que son parent (à l'exception de la racine qui n'a pas de parent).
Une tarte à $k$ pommes est un couple $(v, S)$ où :
- $v \in V$ est un sommet de l'arbre (le centre),
- $S \subset V \setminus \{v\}$ est un ensemble de sommets de taille $k - 1$,
- il existe un entier $d$ tel que pour tout $u \in S$, $\text{dist}(v, u) = d$.
La distance $\text{dist}(u, v)$ est définie comme le nombre d'arêtes sur le chemin simple reliant les sommets $u$ et $v$.
Autrement dit, une tarte à $k$ pommes est constituée d'un sommet $v$ (le centre) et de $k - 1$ autres sommets situés tous à la même distance de $v$.
Votre tâche consiste à calculer le nombre de tartes à $k$ pommes dans l'arbre donné.
Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.
Entrée
Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 10^4$). La description des cas de test suit.
Chaque cas de test commence par une ligne contenant deux entiers $n$ et $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$) : le nombre de sommets dans le pommier et la taille de la tarte aux pommes.
La ligne suivante contient $n - 1$ entiers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), où $p_i$ désigne le parent du sommet $i$ dans le pommier.
La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $5 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez un seul entier : le nombre de tartes à $k$ pommes modulo $998\,244\,353$.
Exemples
Entrée 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Sortie 1
1 20 16
Remarque
Dans le premier cas de test, la seule tarte existante est centrée sur le sommet $1$, et l'ensemble correspondant est $S = \{2, 3\}$.