Aleksei nhận được một cây táo kích thước $n$ làm quà sinh nhật. Là một lập trình viên thi đấu, anh ấy quyết định tính số lượng bánh táo cỡ $k$ ($k$-apple pies) trên cây.
Một cây táo kích thước $n$ được định nghĩa là một cây có gốc gồm $n$ đỉnh, gốc tại đỉnh $1$, trong đó mỗi đỉnh có số con trực tiếp ít hơn hẳn so với cha của nó (ngoại trừ đỉnh gốc không có cha).
Một bánh táo cỡ $k$ là một cặp $(v, S)$ trong đó:
- $v \in V$ là một đỉnh của cây (tâm),
- $S \subset V \setminus \{v\}$ là một tập hợp các đỉnh có kích thước $k - 1$,
- tồn tại một số nguyên $d$ sao cho với mọi $u \in S$, $\text{dist}(v, u) = d$.
Khoảng cách $\text{dist}(u, v)$ được định nghĩa là số cạnh trên đường đi đơn giữa hai đỉnh $u$ và $v$.
Nói cách khác, một bánh táo cỡ $k$ bao gồm một đỉnh $v$ (tâm) và $k - 1$ đỉnh khác đều có cùng khoảng cách đến $v$.
Nhiệm vụ của bạn là tính số lượng bánh táo cỡ $k$ trong cây đã cho.
Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.
Dữ liệu vào
Mỗi test chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 10^4$). Mô tả của các bộ dữ liệu theo sau.
Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa hai số nguyên $n$ và $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): số đỉnh trong cây táo và kích thước của bánh táo.
Dòng tiếp theo chứa $n - 1$ số nguyên $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), trong đó $p_i$ biểu thị cha của đỉnh $i$ trong cây táo.
Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: số lượng bánh táo cỡ $k$ theo modulo $998\,244\,353$.
Ví dụ
Dữ liệu vào 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Dữ liệu ra 1
1 20 16
Ghi chú
Trong bộ dữ liệu đầu tiên, chiếc bánh duy nhất tồn tại có tâm tại đỉnh $1$, và tập hợp tương ứng là $S = \{2, 3\}$.