Олексій отримав на день народження яблуню розміру $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\}$.