409708: GYM103688 J JOJO's Happy Tree Friends

Joseph is playing a game with his friends. The game goes on a tree – a connected graph with $$$n$$$ vertices and $$$n - 1$$$ edges. The vertices are labeled by $$$1,2,\cdots,n$$$. The root of the tree is $$$1$$$.

There is a token initially on one of the vertices. At each step, Joseph will randomly choose a vertex from the $$$n$$$ vertices with equal probability, and then move the token according to the rules as follows:

Assume the token is currently on vertex $$$u$$$. And then vertex $$$v$$$ is selected by Joseph at random

• If $$$u$$$ is an ancestor of $$$v$$$, move the token to the vertex $$$v$$$.
• If $$$u$$$ is not an ancestor of $$$v$$$, move the token to the vertex $$$\texttt{LCA}(u,v)$$$. $$$\texttt{LCA}(u,v)$$$ denotes the lowest common ancestor of vectex $$$u$$$ and $$$v$$$.

There is also a target vertex $$$w$$$ in the tree. As soon as the token is moved to the target vertex, the game is over. Otherwise, the game will keep going until it hits the target vertex.

He wants to know the expected number of steps to hit the target when the token starts from each vertex.

Let's denote the expectation of steps starting from vertex $$$u$$$ modulo $$$10^9 + 7$$$ by $$$E(u)$$$. You are only expected to print $$$$$$ \sum_{u = 1}^{n} E(u) \oplus u $$$$$$

The first line contains one integer $$$n ~ (1 \leq n \leq 2 \times 10^5)$$$, indicating the number of vertices.

The following line contains $$$n-1$$$ integers $$$p_2, p_3, ...., p_n$$$, indicating the parent of each vertex.

The third contains one integer $$$w ~ (1 \leq w \leq n)$$$, indicating the target vertex.

Only one integer – the answer after encrypting. See the description for details.

4
1 2 1
1

333333343

6
1 2 3 4 5
5

23

10
1 2 2 1 5 6 6 8 8
8

3263736426

For the first example, the expected number of steps to hit the target starting from vectices $$$1,2,3,4$$$ are $$$0, 2, 2, \frac{4}{3} \equiv 333333337$$$ respectively.

For the second example, the expectations are $$$6,6,6,6,0,6$$$ respectively.