Problem Description

Vito lives in a city with $n$ parks numbered from $1$ to $n$. These parks are connected by $n-1$ roads such that there is a path between any two parks. Each park has a beauty value, with the $i$-th park having a beauty value of $v_i$.

Last night, Vito decided to take a walk in the city. After visiting a park, he would randomly choose a road and visit the park it leads to. However, he noticed through the windows of a skyscraper that each road had either a blue snake or a red snake. Blue snakes attack anyone traveling from a smaller-numbered park to a larger-numbered park, and red snakes attack anyone traveling from a larger-numbered park to a smaller-numbered park. Since Vito does not want to be attacked by snakes, he decided to only consider roads that would not lead to an attack. He likes long walks, so he will not stop until there is at least one safe road he can take.

When Vito went downstairs, he completely forgot which roads had red or blue snakes. Therefore, he wants to know: "If each road has an equal probability of having a blue or red snake, what is the expected beauty of the path I take starting from the $i$-th park?"

The beauty of a path is the sum of the beauty values of the parks visited along the path. The expected beauty of a path is defined as the sum of the beauty of the path multiplied by the probability of Vito taking that path, over all possible paths.

Input Format

The first line contains an integer $n\ (2\le n\le 10^6)$, the number of parks.

The second line contains $n-1$ integers $p_i\ (1\le p_i<i)$, indicating that there is a road between the $(i+1)$-th park and the $p_i$-th park.

The third line contains $n$ integers $v_i\ (0\le v_i\le 10^6)$, the beauty values of the parks.

Output Format

For each $i$-th line, output the expected beauty of the path starting from the $i$-th park. If this value is $\frac{a}{b}$ where $a$ and $b$ are integers, output $ab^{-1} \pmod{10^9+7}$, where $b^{-1}$ is the modular inverse of $b$ modulo $10^9+7$.

Sample Input and Output

Input Sample #1

2
1
2 1

Output Sample #1

500000006
2

Input Sample #2

3
1 1
8 8 8

Output Sample #2

14
14
14

Input Sample #3

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

Output Sample #3

968750272
610352580
450521029
536458466
199219275
662760680
190972315
90277951
824219264
941840425
532552597

Notes/Hints

Sample Explanation 1

The expected beauty of the path starting from the first park is $2.5\pmod{10^9+7}=\frac{5}{2}\pmod{10^9+7}=5\cdot 2^{-1}\pmod{10^9+7}=5\cdot 500000004\pmod{10^9+7}=500000006\pmod{10^9+7}$, and the expected beauty of the path starting from the second park is $2$.

Sample Explanation 2

The probability that both snakes are red is $\frac{1}{4}$. In this case, if Vito starts from the first park, he will randomly choose which road to take.

Subtasks

见题面 Input 部分

见题面 Output 部分