Random tree#11054
Consider the following process of building a tree .
Initially, the tree consists of one vertex, which has the number .
Further vertices with numbers ... are added to the tree.
At the -th step, a vertex with number i + 1 is added to the tree, and an edge from it to some already added vertex (1 \leq p \leq i), which is chosen among them randomly with equal probability.
Let be the set of vertices already added to .
Then let be the number of vertices in that lie either in or on the path between any two vertices from (perhaps both here and there).
After adding each vertex, your task is to print the sum over all sets , which are subsets of the set of vertices already added to ( over all A \subset V). Since the answers can be very large, print only the remainder of the answer divided by .
The first line contains a single number (2 \leq n \leq 200000) - the number of vertices in the tree after the last step.
The next line contains n - 1 integers p_1, p_2, \ldots, p_{n-1} (1 \leq p_i \leq i), denoting adding to the graph the vertex i + 1 and the edge between p_i and i + 1, respectively. It is guaranteed that p_i is chosen randomly with equal probability among the numbers from to .
Print n - 1 integers - the remainders from division ( over all A \subset V) by after adding each vertex.
Example 1
Example 2