G. Короткая гирлянда
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп хочет повесить гирлянду на ёлку.

Ёлка — это корневое дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Расстояние между двумя вершинами ёлки — это количество рёбер на кратчайшем пути между ними, а глубина вершины ёлки — расстояние от неё до корня.

Гирлянда состоит из $$$n$$$ лампочек, соединённых проводом и пронумерованных от $$$1$$$ до $$$n$$$. Длина части провода между каждыми двумя соседними лампочками равна $$$k$$$.

Гирлянда должна быть повешена на ёлку по следующим правилам:

  • каждая лампочка должна быть повешена на одну из вершин ёлки, при этом на каждой вершине должна оказаться лампочка;
  • лампочка $$$1$$$ должна быть повешена на корень ёлки;
  • каждая следующая лампочка вешается на вершину, на родителя которого уже повешена лампочка. Если таких вершин несколько — выбирается вершина с наибольшей глубиной. Если таких всё ещё несколько — можно выбрать любую из них;
  • для каждой пары соседних лампочек расстояние между вершинами, на которые они повешены, не должно превышать $$$k$$$.

Ваша задача — посчитать количество способов повесить гирлянду, соблюдая все правила, и вывести его по модулю $$$998244353$$$. Два способа являются различными, если существует хотя бы одно такое число $$$i \in [1, n]$$$, что $$$i$$$-я лампочка находится на разных вершинах в этих двух способах.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \lt n$$$) — количество вершин в ёлке и ограничение на расстояние между двумя соседними лампочками.

Во второй строке записаны $$$n-1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$), где $$$p_i$$$ — родитель $$$i$$$-й вершины в ёлке.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — количество способов повесить гирлянду, соблюдая все правила, по модулю $$$998244353$$$.

Пример
Входные данные
4
5 1
1 1 2 2
5 2
1 1 2 2
5 3
1 1 2 2
8 4
1 1 3 2 3 1 4
Выходные данные
0
2
4
12