Aleksei fikk et epletre av størrelse $n$ i bursdagsgave. Som konkurranseprogrammerer bestemte han seg for å beregne antallet $k$-eplepaier i treet.
Et epletre av størrelse $n$ er definert som et rotfestet tre med $n$ noder, med rot i node $1$, der hver node har strengt færre direkte barn enn forelderen sin (bortsett fra roten, som ikke har noen forelder).
En $k$-eplepai er et par $(v, S)$ der:
- $v \in V$ er en node i treet (sentrum),
- $S \subset V \setminus \{v\}$ er en mengde noder med størrelse $k - 1$,
- det finnes et heltall $d$ slik at for enhver $u \in S$ gjelder $\text{dist}(v, u) = d$.
Avstanden $\text{dist}(u, v)$ er definert som antallet kanter på den enkle stien mellom nodene $u$ og $v$.
Med andre ord består en $k$-eplepai av én node $v$ (sentrum) og $k - 1$ andre noder som alle ligger i samme avstand fra $v$.
Oppgaven din er å beregne antallet $k$-eplepaier i det gitte treet.
Siden svaret kan være stort, skal du skrive det ut modulo $998\,244\,353$.
Inndata
Hver test inneholder flere testtilfeller. Den første linjen inneholder antallet testtilfeller $t$ ($1 \le t \le 10^4$). Beskrivelsen av testtilfellene følger.
Hvert testtilfelle begynner med en linje som inneholder to heltall $n$ og $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): antallet noder i epletreet og størrelsen på eplepaien.
Den neste linjen inneholder $n - 1$ heltall $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), der $p_i$ angir forelderen til node $i$ i epletreet.
Summen av $n$ over alle testtilfeller overstiger ikke $5 \cdot 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut ett enkelt heltall: antallet $k$-eplepaier modulo $998\,244\,353$.
Eksempler
Inndata 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Utdata 1
1 20 16
Forklaring
I det første testtilfellet har den eneste eksisterende paien sentrum i node $1$, og den tilhørende mengden er $S = \{2, 3\}$.