Aleksei ha ricevuto un melo di dimensione $n$ come regalo di compleanno. Essendo lui stesso un programmatore competitivo, ha deciso di calcolare il numero di torte di $k$ mele presenti sull'albero.
Un melo di dimensione $n$ è definito come un albero radicato con $n$ vertici, con radice nel vertice $1$, in cui ogni vertice ha strettamente meno figli diretti rispetto a suo padre (eccetto la radice, che non ha alcun padre).
Una torta di $k$ mele è una coppia $(v, S)$ dove:
- $v \in V$ è un vertice dell'albero (il centro),
- $S \subset V \setminus \{v\}$ è un insieme di vertici di dimensione $k - 1$,
- esiste un intero $d$ tale che per ogni $u \in S$ vale $\text{dist}(v, u) = d$.
La distanza $\text{dist}(u, v)$ è definita come il numero di archi sul cammino semplice tra i vertici $u$ e $v$.
In altre parole, una torta di $k$ mele è formata da un vertice $v$ (il centro) e da altri $k - 1$ vertici che si trovano tutti alla stessa distanza da $v$.
Il tuo compito è calcolare il numero di torte di $k$ mele nell'albero dato.
Poiché la risposta può essere molto grande, stampala modulo $998\,244\,353$.
Input
Ogni test contiene più casi di test. La prima riga contiene il numero di casi di test $t$ ($1 \le t \le 10^4$). Segue la descrizione dei casi di test.
Ogni caso di test inizia con una riga contenente due interi $n$ e $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): il numero di vertici nel melo e la dimensione della torta di mele.
La riga successiva contiene $n - 1$ interi $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), dove $p_i$ indica il padre del vertice $i$ nel melo.
La somma di $n$ su tutti i casi di test non supera $5 \cdot 10^5$.
Output
Per ogni caso di test, stampa un singolo intero: il numero di torte di $k$ mele modulo $998\,244\,353$.
Esempi
Input 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Output 1
1 20 16
Note
Nel primo caso di test, l'unica torta esistente è centrata nel vertice $1$ e l'insieme corrispondente è $S = \{2, 3\}$.