409708: GYM103688 J JOJO's Happy Tree Friends

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. JOJO's Happy Tree Friendstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 $$$$$$

Input

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.

Output

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

ExamplesInput
4
1 2 1
1
Output
333333343
Input
6
1 2 3 4 5
5
Output
23
Input
10
1 2 2 1 5 6 6 8 8
8
Output
3263736426
Note

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.

加入题单

上一题 下一题 算法标签: