Алексей получил на день рождения яблоню размера $n$. Будучи спортивным программистом, он решил посчитать количество $k$-яблочных пирогов на этом дереве.
Яблоней размера $n$ называется подвешенное дерево из $n$ вершин с корнем в вершине $1$, в котором у каждой вершины строго меньше непосредственных сыновей, чем у её родителя (за исключением корня, у которого нет родителя).
$k$-яблочным пирогом называется пара $(v, S)$, где:
- $v \in V$ — вершина дерева (центр),
- $S \subset V \setminus \{v\}$ — множество вершин размера $k - 1$,
- существует такое целое число $d$, что для каждой вершины $u \in S$ выполняется $\text{dist}(v, u) = d$.
Расстояние $\text{dist}(u, v)$ определяется как количество рёбер на простом пути между вершинами $u$ и $v$.
Иными словами, $k$-яблочный пирог состоит из одной вершины $v$ (центра) и $k - 1$ других вершин, находящихся на одном и том же расстоянии от $v$.
Ваша задача — вычислить количество $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$.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество $k$-яблочных пирогов по модулю $998\,244\,353$.
Примеры
Входные данные 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\}$.