Aleksei menerima sebuah pohon apel berukuran $n$ sebagai hadiah ulang tahun. Sebagai seorang pemrogram kompetitif, ia memutuskan untuk menghitung banyaknya pai apel-$k$ ($k$-apple pies) pada pohon tersebut.
Sebuah pohon apel berukuran $n$ didefinisikan sebagai pohon berakar dengan $n$ simpul, berakar di simpul $1$, di mana setiap simpul memiliki anak langsung yang lebih sedikit secara ketat daripada induknya (kecuali akar yang tidak memiliki induk).
Sebuah pai apel-$k$ adalah pasangan $(v, S)$ di mana:
- $v \in V$ adalah sebuah simpul dari pohon (pusat),
- $S \subset V \setminus \{v\}$ adalah himpunan simpul berukuran $k - 1$,
- terdapat sebuah bilangan bulat $d$ sedemikian sehingga untuk setiap $u \in S$, berlaku $\text{dist}(v, u) = d$.
Jarak $\text{dist}(u, v)$ didefinisikan sebagai banyaknya sisi pada lintasan sederhana antara simpul $u$ dan $v$.
Dengan kata lain, sebuah pai apel-$k$ terdiri atas satu simpul $v$ (pusat) dan $k - 1$ simpul lainnya yang semuanya berada pada jarak yang sama dari $v$.
Tugas Anda adalah menghitung banyaknya pai apel-$k$ pada pohon yang diberikan.
Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.
Masukan
Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $t$ ($1 \le t \le 10^4$). Deskripsi dari masing-masing kasus uji menyusul.
Setiap kasus uji dimulai dengan satu baris yang berisi dua bilangan bulat $n$ dan $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): banyaknya simpul pada pohon apel dan ukuran pai apel.
Baris berikutnya berisi $n - 1$ bilangan bulat $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), di mana $p_i$ menyatakan induk dari simpul $i$ pada pohon apel.
Jumlah $n$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.
Keluaran
Untuk setiap kasus uji, keluarkan satu bilangan bulat: banyaknya pai apel-$k$ modulo $998\,244\,353$.
Contoh
Masukan 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Keluaran 1
1 20 16
Catatan
Pada kasus uji pertama, satu-satunya pai yang ada berpusat di simpul $1$, dan himpunan yang bersesuaian adalah $S = \{2, 3\}$.