Vito lives in a city with \(n\) parks labeled from 1 to \(n\). The parks are connected
with \(n - 1\) roads such that there is a path between any two pairs of parks. Every
park has some beauty value, beauty value of \(i-th\) park is \(v\)\(i\).
Last night Vito decided to wander around the city in such a way that after he
visits a park he chooses a random road with equal probability and visits a park
to which that road leads. But before he started his journey he looked through the
window of his skyscraper and saw that on every road there is either a blue or a red
snake. Blue snakes attack all people traveling from the park with a lower label to a park with a higher
one, a red snakes attack everyone traveling from a park with higher label to lower. As Vito doesn’t want
to get attacked by a snake he decided to change his plans by considering only roads on which he will not
get attacked by a snake when choosing a random road. Since he likes long walks he will not stop on his
journey until there is at least one road he can safely pass.
And while Vito walks down the stairs of his skyscraper he completely forgot on which road is red or blue
snake so he wonders: \(If\) \(on\) every road there \(is\) \(an\) equal probability \(of\) \(a\) blue \(or\) \(a\) red snake, what \(is\) the
expected beauty \(of\) \(my\) journey which starts \(in\) the \(i-th\) park?
Beauty of path is the sum of beauties of parks visited on that journey. Expected beauty of journey is
defined as the sum of product of beauty of a path and probability Vito takes that path, for every possible
path.

Subtask 1 (10 points): \(n \le 10\)

Subtask 2 (30 points): \(n \le 1000\)

Subtask 3 (30 points): In sequence \(p_{i}\) no value is present more than 2 times.

Subtask 4 (40 points): No additional constraints. If your program, on some test, outputs the first line correct, but outputs a wrong answer in the following lines, it will receive 50% of points for that test. The number of points in a subtask corresponds to the least number of points achieved by some test in that subtask. Probni primjeri input

Subtask 2 (1 points): 2 1 output

Subtask 500000006 (2 points): input 3 1 1 8 8 8 output

Subtask 14 (14 points): 14 input 11 1 1 1 2 3 4 1 2 6 2 1 1000 5 3 18 200 8 9 0 2 2 output

Subtask 968750272 (610352580 points): —

Subtask 450521029 (536458466 points): —

Subtask 199219275 (662760680 points): —

Subtask 190972315 (90277951 points): —

Subtask 824219264 (941840425 points): 532552597 Clarification of the first example: The expected beauty of a journey starting at the first park is 2.5 (mod \(10^{9}+7\)) = ^{5} {2} ^{{(} {10}}}^{+7) = 5^{·}{−} } (mod \(10^{9} + 7\)) = \(5 \cdot 500000004\) (mod \(10^{9} + 7\)) = 500000006 (mod \(10^{9} + 7\)) and starting from the second park it is 2. Clarification of the second example: Probability that both snakes are red is ^{1 chooses which road he will take.} ^{and} ^{in} ^{that} ^{case} ^{if} ^{Vito} ^{starts} ^{at} ^{the} ^{first} ^{park} ^{he} ^{randomly

In the first line there is an integer \(n\) (\(2 \le n \le 10^{6}\)), which denotes the number of parks.
In the second line there are \(n - 1\) integers \(p@@RISE_MATH_BLOCK_0@@i < i\)), which denote a road between the (\(i + 1\))-th
park and \(p_{i}-th\) park.
In the third line there are \(n\) integers \(v@@RISE_MATH_BLOCK_1@@i \le 10^{6}\)), where \(v\)\(i\) denotes the beauty of \(i-th\) park.

If expected beauty of Vito’s journey which starts at \(i-th\) park is ^{a}
_{b} ^{for} ^{integers} ^{a} ^{and} ^{b} } ^{then} ^{in^{i}} ^{line} ^{of
output print \(ab\)^{−} (mod \(10^{9} + 7\)) where \(b\)^{−} is modular inverse of \(b\) (mod \(10^{9} + 7\)).

생성자가 기록되지 않았습니다.

출처 COCI 2023/2024 Contest 3