Aleksei hat zum Geburtstag einen Apfelbaum der Größe $n$ geschenkt bekommen. Da er selbst Wettbewerbsprogrammierer ist, beschloss er, die Anzahl der $k$-Apfelkuchen auf dem Baum zu berechnen.
Ein Apfelbaum der Größe $n$ ist definiert als ein gewurzelter Baum mit $n$ Knoten und Wurzel im Knoten $1$, bei dem jeder Knoten echt weniger direkte Kinder hat als sein Elternknoten (mit Ausnahme der Wurzel, die keinen Elternknoten besitzt).
Ein $k$-Apfelkuchen ist ein Paar $(v, S)$, wobei:
- $v \in V$ ein Knoten des Baumes ist (das Zentrum),
- $S \subset V \setminus \{v\}$ eine Menge von Knoten der Größe $k - 1$ ist,
- eine ganze Zahl $d$ existiert, sodass für alle $u \in S$ gilt: $\text{dist}(v, u) = d$.
Der Abstand $\text{dist}(u, v)$ ist definiert als die Anzahl der Kanten auf dem einfachen Pfad zwischen den Knoten $u$ und $v$.
Mit anderen Worten: Ein $k$-Apfelkuchen besteht aus einem Knoten $v$ (dem Zentrum) und $k - 1$ weiteren Knoten, die alle denselben Abstand zu $v$ haben.
Deine Aufgabe ist es, die Anzahl der $k$-Apfelkuchen im gegebenen Baum zu berechnen.
Da die Antwort sehr groß sein kann, gib sie modulo $998\,244\,353$ aus.
Eingabe
Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält die Anzahl der Testfälle $t$ ($1 \le t \le 10^4$). Es folgt die Beschreibung der Testfälle.
Jeder Testfall beginnt mit einer Zeile mit zwei ganzen Zahlen $n$ und $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): der Anzahl der Knoten im Apfelbaum und der Größe des Apfelkuchens.
Die nächste Zeile enthält $n - 1$ ganze Zahlen $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), wobei $p_i$ den Elternknoten von Knoten $i$ im Apfelbaum bezeichnet.
Die Summe von $n$ über alle Testfälle hinweg überschreitet nicht $5 \cdot 10^5$.
Ausgabe
Gib für jeden Testfall eine einzige ganze Zahl aus: die Anzahl der $k$-Apfelkuchen modulo $998\,244\,353$.
Beispiele
Eingabe 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Ausgabe 1
1 20 16
Hinweis
Im ersten Testfall hat der einzige existierende Kuchen sein Zentrum im Knoten $1$, und die zugehörige Menge ist $S = \{2, 3\}$.