Aleksei sai syntymäpäivälahjaksi omenapuun, jonka koko on $n$. Kilpaohjelmoijana hän päätti laskea puussa olevien $k$-omenapiirakoiden lukumäärän.
Kokoa $n$ oleva omenapuu määritellään $n$-solmuiseksi juurelliseksi puuksi, jonka juuri on solmu $1$ ja jossa jokaisella solmulla on aidosti vähemmän suoria lapsia kuin sen vanhemmalla (lukuun ottamatta juurta, jolla ei ole vanhempaa).
$k$-omenapiirakka on pari $(v, S)$, missä:
- $v \in V$ on puun solmu (keskus),
- $S \subset V \setminus \{v\}$ on solmujen joukko, jonka koko on $k - 1$,
- on olemassa sellainen kokonaisluku $d$, että kaikilla $u \in S$ pätee $\text{dist}(v, u) = d$.
Etäisyys $\text{dist}(u, v)$ määritellään solmujen $u$ ja $v$ välisen yksinkertaisen polun kaarien lukumääräksi.
Toisin sanoen $k$-omenapiirakka koostuu yhdestä solmusta $v$ (keskuksesta) sekä $k - 1$ muusta solmusta, jotka ovat kaikki samalla etäisyydellä solmusta $v$.
Tehtäväsi on laskea $k$-omenapiirakoiden lukumäärä annetussa puussa.
Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.
Syöte
Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten lukumäärän $t$ ($1 \le t \le 10^4$). Seuraavaksi annetaan testitapausten kuvaukset.
Jokainen testitapaus alkaa rivillä, joka sisältää kaksi kokonaislukua $n$ ja $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): omenapuun solmujen lukumäärän ja omenapiirakan koon.
Seuraava rivi sisältää $n - 1$ kokonaislukua $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), missä $p_i$ tarkoittaa solmun $i$ vanhempaa omenapuussa.
Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi kokonaisluku: $k$-omenapiirakoiden lukumäärä modulo $998\,244\,353$.
Esimerkit
Syöte 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Tuloste 1
1 20 16
Huomautus
Ensimmäisessä testitapauksessa ainoa olemassa oleva piirakka on keskittynyt solmuun $1$, ja sitä vastaava joukko on $S = \{2, 3\}$.