D. Прыжки по дереву
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано корневое дерево, состоящее из $$$n$$$ вершин. Вершины в дереве пронумерованы от $$$1$$$ до $$$n$$$, корень дерева – вершина $$$1$$$. Пусть $$$d_x$$$ — это расстояние (количество ребер на кратчайшем пути) от корня до вершины $$$x$$$.

Есть фишка, которая изначально расположена в корне. Вы можете выполнять следующую операцию столько раз, сколько захотите (возможно, ноль):

  • переместить фишку из текущей вершины $$$v$$$ в вершину $$$u$$$, такую что $$$d_u = d_v + 1$$$. Если $$$v$$$ — это корень, вы можете выбрать любую вершину $$$u$$$, соответствующую этому условию; однако, если $$$v$$$ не является корнем, $$$u$$$ не должен быть соседом $$$v$$$ (между $$$v$$$ и $$$u$$$ не должно быть ребра).

Например, в приведённом выше дереве возможны следующие перемещения фишки: $$$1 \rightarrow 2$$$, $$$1 \rightarrow 5$$$, $$$2 \rightarrow 7$$$, $$$5 \rightarrow 3$$$, $$$5 \rightarrow 4$$$, $$$3 \rightarrow 6$$$, $$$7 \rightarrow 6$$$.

Последовательность вершин является допустимой, если вы можете перемещать фишку таким образом, чтобы она посетила все вершины из последовательности (и только их), в порядке, в котором они даны в последовательности.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

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

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

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

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

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

В первом примере допустимы следующие последовательности: $$$[1]$$$, $$$[1, 2]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$.

Во втором примере допустимы следующие последовательности: $$$[1]$$$, $$$[1, 2]$$$.

В третьем примере допустимы следующие последовательности: $$$[1]$$$, $$$[1, 2]$$$, $$$[1, 2, 7]$$$, $$$[1, 2, 7, 6]$$$, $$$[1, 5]$$$, $$$[1, 5, 3]$$$, $$$[1, 5, 3, 6]$$$, $$$[1, 5, 4]$$$.