Алексей туған күніне сыйлық ретінде өлшемі $n$ болатын алма ағашын алды. Спорттық бағдарламашы ретінде ол ағаштағы $k$-алма бәліштерінің санын есептеуді ұйғарды.
Өлшемі $n$ болатын алма ағашы деп төбесі $1$-де орналасқан, $n$ төбеден тұратын түбірлі ағаш аталады, мұнда әрбір төбенің тікелей ұрпақтарының саны оның ата-анасының тікелей ұрпақтарының санынан қатаң түрде аз (ата-анасы жоқ түбірден басқа).
$k$-алма бәліші — бұл $(v, S)$ жұбы, мұндағы:
- $v \in V$ — ағаштың төбесі (орталығы),
- $S \subset V \setminus \{v\}$ — өлшемі $k - 1$ болатын төбелер жиыны,
- әрбір $u \in S$ үшін $\text{dist}(v, u) = d$ орындалатындай бүтін $d$ саны табылады.
$\text{dist}(u, v)$ арақашықтығы $u$ мен $v$ төбелерінің арасындағы қарапайым жолдағы қырлар саны ретінде анықталады.
Басқаша айтқанда, $k$-алма бәліші бір $v$ төбесінен (орталықтан) және $v$ төбесінен бірдей қашықтықта орналасқан басқа $k - 1$ төбеден тұрады.
Сіздің міндетіңіз — берілген ағаштағы $k$-алма бәліштерінің санын есептеу.
Жауап өте үлкен болуы мүмкін болғандықтан, оны $998\,244\,353$ модулі бойынша шығарыңыз.
Кіріс деректері
Әрбір тест бірнеше тест жиынтығынан тұрады. Бірінші жолда тест жиынтықтарының саны $t$ ($1 \le t \le 10^4$) берілген. Одан кейін тест жиынтықтарының сипаттамасы беріледі.
Әрбір тест жиынтығы екі бүтін сан $n$ мен $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$) жазылған жолдан басталады: алма ағашындағы төбелер саны және алма бәлішінің өлшемі.
Келесі жолда $n - 1$ бүтін сан $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) берілген, мұндағы $p_i$ алма ағашындағы $i$ төбесінің ата-анасын білдіреді.
Барлық тест жиынтықтары бойынша $n$ қосындысы $5 \cdot 10^5$-нен аспайды.
Шығыс деректері
Әрбір тест жиынтығы үшін бір бүтін санды шығарыңыз: $998\,244\,353$ модулі бойынша $k$-алма бәліштерінің саны.
Мысалдар
Кіріс деректері 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Шығыс деректері 1
1 20 16
Ескертпе
Бірінші тест жиынтығында бар жалғыз бәліштің орталығы $1$-ші төбеде орналасқан, ал оған сәйкес жиын $S = \{2, 3\}$.