Случайное дерево
Рассмотрим следующий процесс построения дерева T.
Изначально дерево состоит из одной вершины, которая имеет номер 1.
Дальше в дерево добавляются вершины с номерами 2 ... n.
На i-м шаге в дерево добавляется вершина с номером i + 1, также в дерево добавляется ребро из нее в некоторую уже добавленную вершину p (1 ≤ p ≤ i), которая выбирается среди них случайно равновероятно.
Пусть V - множество уже добавленных в T вершин.
Тогда пусть f(A) - количество вершин T, что они лежат или в A, или на пути между какими-либо двумя вершинами из A (возможно, и там, и там).
Ваша задача после добавления каждой вершины вывести сумму f(A) по всем множествам A, которые являются подмножествами множества уже добавленных в T вершин (Σ f(A) по всем A ⊂ V). Так как ответы могут быть очень большим, выводите лишь остатки от деления ответа на 998244353.
Входные данные
Первая строка содержит одно число n (2 ≤ n ≤ 200000) - количество вершин в дереве после последнего шага.
В следующей строке расположено n - 1 целое число p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ i), обозначающих добавления в граф вершины i + 1 и ребра между p[i] и i + 1 соответственно. Гарантируется, что p[i] выбрано случайно равновероятно среди чисел от 1 до i.
Выходные данные
Выведите n - 1 целое число, остатки от деления (Σ f(A) по всем A ⊂ V) на 998244353 после добавления каждой вершины.
