Випадкове дерево#11054
Розгляньмо процес побудови дерева .
Спочатку дерево складається лише з однієї вершини з номером .
Потім у дерево додаються вершини з номерами від до .
На -му кроці додається вершина з номером i + 1 і ребро, що з'єднує її з однією з уже доданих вершин (1 \leq p \leq i), яка вибирається випадково з рівною ймовірністю.
Нехай - множина вже доданих у вершин.
Визначимо як кількість вершин у , які або належать , або лежать на шляху між будь-якими двома вершинами з (можливо, і там, і там).
Ваше завдання - після додавання кожної вершини вивести суму для всіх підмножин множини ( для всіх A \subset V). Оскільки результати можуть бути дуже великими, виводьте лише залишки від ділення на .
Перший рядок містить одне число (2 \leq n \leq 200000) - кількість вершин у дереві після завершення процесу.
У наступному рядку наведено n - 1 ціле число p_1, p_2, \ldots, p_{n-1} (1 \leq p_i \leq i), що вказують на додавання вершини i + 1 і ребра між p_i та i + 1. Гарантується, що p_i вибрано випадково з рівною ймовірністю серед чисел від до .
Виведіть n - 1 ціле число - залишки від ділення ( для всіх A \subset V) на після додавання кожної вершини.
Приклад 1
Приклад 2