Случайное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующий процесс построения дерева $$$T$$$.

Изначально дерево состоит из одной вершины, которая имеет номер $$$1$$$.

Дальше в дерево добавляются вершины с номерами $$$2 \ldots n$$$.

На $$$i$$$-м шаге в дерево добавляется вершина с номером $$$i+1$$$, также в дерево добавляется ребро из нее в некоторую уже добавленную вершину $$$p$$$ ($$$1 \leq p \leq i$$$), которая выбирается среди них случайно равновероятно.

Пусть $$$V$$$ — множество уже добавленных в $$$T$$$ вершин.

Тогда пусть $$$f(A)$$$ — количество вершин $$$T$$$, что они лежат или в $$$A$$$, или на пути между какими-либо двумя вершинами из $$$A$$$ (возможно, и там, и там).

Ваша задача после добавления каждой вершины вывести сумму $$$f(A)$$$ по всем множествам $$$A$$$, которые являются подмножествами множества уже добавленных в $$$T$$$ вершин ($$$\sum{f(A)}$$$ по всем $$$A \subseteq V$$$). Так как ответы могут быть очень большим, выводите лишь остатки от деления ответа на $$$998244353$$$.

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

Первая строка входного файла содержит одно число $$$n$$$ — количество вершин в дереве после последнего шага $$$(2 \leq n \leq 200000)$$$.

В следующей строке расположено $$$n-1$$$ целое число $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq i$$$), обозначающих добавления в граф вершины $$$i+1$$$ и ребра между $$$p_i$$$ и $$$i+1$$$ соответственно. Гарантируется, что $$$p_i$$$ выбрано случайно равновероятно среди чисел от $$$1$$$ до $$$i$$$.

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

Выведите $$$n-1$$$ целое число, остатки от деления ($$$\sum{f(A)}$$$ по всем $$$A \subseteq V$$$) на $$$998244353$$$ после добавления каждой вершины.

Примеры

Входные данные
5
1 1 1 1
Выходные данные
4 13 36 91 
Входные данные
7
1 2 3 4 5 6
Выходные данные
4 13 38 103 264 649 

Примечание

Итоговые деревья из примеров: