Slučajna Cesta

문제

Vito lives in a city with $nn$ parks labeled from $11$ to $nn$. The parks are connected with $n-1n\; -\; 1$ roads such that there is a path between any two pairs of parks. Every park has some beauty value, beauty value of $ii$-th park is $v_{i}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 $ii$-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.

입력

In the first line there is an integer $nn$ (2 ≤ n ≤ 10^6), which denotes the number of parks.

In the second line there are $n-1n\; -\; 1$ integers $p_{i}p\_i$ (1 &le; p_i < i), which denote a road between the $(i+1)(i\; +\; 1)$-th park and $p_{i}p\_i$-th park.

In the third line there are $nn$ integers $v_{i}v\_i$ (0 &le; v_i &le; 10^6), where $v_{i}v\_i$ denotes the beauty of $ii$-th park.

출력

If expected beauty of Vito’s journey which starts at $ii$-th park is $\frac{a}{b}\backslash frac\{a\}\{b\}$ for integers $aa$ and $bb$, then in $ii$-th line of output print $a{b}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)ab^\{-1\}\; \backslash pmod\; \{10^9\; +\; 7\}$ where $b^{-1}b^\{-1\}$ is modular inverse of $b(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)b\; \backslash pmod\; \{10^9\; +\; 7\}$.

힌트

Clarification of the first example:

The expected beauty of a journey starting at the first park is $2.5(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)=\frac{5}{2}(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)=5\cdot 2^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)=5\cdot 500000004(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)=500000006(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)2.5\; \backslash pmod\; \{10^9\; +\; 7\}\; =\; \backslash frac\{5\}\{2\}\; \backslash pmod\; \{10^9\; +\; 7\}\; =\; 5\; \backslash cdot\; 2\; ^\{-1\}\; \backslash pmod\; \{10^9\; +\; 7\}\; =\; 5\; \backslash cdot\; 500000004\; \backslash pmod\; \{10^9\; +\; 7\}\; =\; 500000006\; \backslash pmod\; \{10^9\; +\; 7\}$ and starting from the second park it is $22$.

Clarification of the second example:

Probability that both snakes are red is $\frac{1}{4}\backslash frac\{1\}\{4\}$ and in that case if Vito starts at the first park he randomly chooses which road he will take.

2
1
2 1

500000006
2

3
1 1
8 8 8

14
14
14

11
1 1 1 2 3 4 1 2 6 2
1 1000 5 3 18 200 8 9 0 2 2

968750272
610352580
450521029
536458466
199219275
662760680
190972315
90277951
824219264
941840425
532552597