Aleksei fick ett äppelträd av storlek $n$ i födelsedagspresent. Som tävlingsprogrammerare bestämde han sig för att beräkna antalet $k$-äppelpajer i trädet.
Ett äppelträd av storlek $n$ definieras som ett rotat träd med $n$ hörn, med rot i hörn $1$, där varje hörn har strikt färre direkta barn än sin förälder (förutom roten som inte har någon förälder).
En $k$-äppelpaj är ett par $(v, S)$ där:
- $v \in V$ är ett hörn i trädet (centrum),
- $S \subset V \setminus \{v\}$ är en mängd hörn av storlek $k - 1$,
- det finns ett heltal $d$ sådant att för varje $u \in S$ gäller $\text{dist}(v, u) = d$.
Avståndet $\text{dist}(u, v)$ definieras som antalet kanter på den enkla vägen mellan hörnen $u$ och $v$.
Med andra ord består en $k$-äppelpaj av ett hörn $v$ (centrum) och $k - 1$ andra hörn som alla ligger på samma avstånd från $v$.
Din uppgift är att beräkna antalet $k$-äppelpajer i det givna trädet.
Eftersom svaret kan vara stort ska du skriva ut det modulo $998\,244\,353$.
Indata
Varje test innehåller flera testfall. Den första raden innehåller antalet testfall $t$ ($1 \le t \le 10^4$). Beskrivningen av testfallen följer.
Varje testfall börjar med en rad som innehåller två heltal $n$ och $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): antalet hörn i äppelträdet och storleken på äppelpajen.
Nästa rad innehåller $n - 1$ heltal $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), där $p_i$ betecknar föräldern till hörn $i$ i äppelträdet.
Summan av $n$ över alla testfall överstiger inte $5 \cdot 10^5$.
Utdata
För varje testfall, skriv ut ett enda heltal: antalet $k$-äppelpajer modulo $998\,244\,353$.
Exempel
Indata 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Utdata 1
1 20 16
Förklaring
I det första testfallet har den enda existerande pajen sitt centrum i hörn $1$, och motsvarande mängd är $S = \{2, 3\}$.