Aleksei fékk eplatré af stærð $n$ í afmælisgjöf. Sem keppnisforritari ákvað hann að reikna fjölda $k$-eplabaka á trénu.
Eplatré af stærð $n$ er skilgreint sem rótað tré með $n$ hnútum, með rót í hnúti $1$, þar sem hver hnútur á strangt færri bein börn en foreldri sitt (nema rótin sem á ekkert foreldri).
$k$-eplabaka er par $(v, S)$ þar sem:
- $v \in V$ er hnútur í trénu (miðjan),
- $S \subset V \setminus \{v\}$ er mengi hnúta af stærð $k - 1$,
- til er heiltala $d$ þannig að fyrir sérhvert $u \in S$ gildir $\text{dist}(v, u) = d$.
Fjarlægðin $\text{dist}(u, v)$ er skilgreind sem fjöldi leggja á einfalda veginum milli hnútanna $u$ og $v$.
Með öðrum orðum samanstendur $k$-eplabaka af einum hnúti $v$ (miðjunni) og $k - 1$ öðrum hnútum sem eru allir í sömu fjarlægð frá $v$.
Verkefni þitt er að reikna fjölda $k$-eplabaka í gefna trénu.
Þar sem svarið getur verið stórt skal prenta það modulo $998\,244\,353$.
Inntak
Hvert próf inniheldur mörg prófunartilfelli. Fyrsta línan inniheldur fjölda prófunartilfella $t$ ($1 \le t \le 10^4$). Lýsing á prófunartilfellunum fylgir.
Hvert prófunartilfelli byrjar á línu sem inniheldur tvær heiltölur $n$ og $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): fjölda hnúta í eplatrénu og stærð eplabökunnar.
Næsta lína inniheldur $n - 1$ heiltölur $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), þar sem $p_i$ táknar foreldri hnúts $i$ í eplatrénu.
Summa $n$ yfir öll prófunartilfelli fer ekki yfir $5 \cdot 10^5$.
Úttak
Fyrir hvert prófunartilfelli skal prenta eina heiltölu: fjölda $k$-eplabaka modulo $998\,244\,353$.
Dæmi
Inntak 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Úttak 1
1 20 16
Skýring
Í fyrsta prófunartilfellinu hefur eina bakan sem er til miðju í hnúti $1$, og samsvarandi mengi er $S = \{2, 3\}$.