Problem Description

Given a rooted tree with $n$ nodes, where $1$ is the root, and $fa_u$ denotes the parent of node $u$. Additionally, a weight sequence $b$ of length $n$ is provided.

A permutation $a$ of length $n$ is considered a valid topological order for this tree if and only if $\forall 2 \le u \le n, a_u > a_{fa_u}$.

For each node $u$, define $f(u)$ as the sum of $b_{a_u}$ across all valid topological orders of the tree.

Now, for $1 \le u \le n$, compute $f(u) \bmod 10^9+7$.

Input Format

The first line contains an integer $n$, representing the number of nodes in the tree.

The second line contains $n-1$ integers, where the $i$-th integer denotes $fa_{i+1}$, describing the structure of the tree.

The third line contains $n$ integers, where the $i$-th integer denotes $b_i$, describing the weight sequence.

Output Format

A single line containing $n$ integers, where the $i$-th integer represents $f(i) \bmod 10^9+7$.

Sample Input and Output

Sample Input #1

5
1 1 3 2
3 5 4 4 1

Sample Output #1

18 27 27 15 15

Sample Input #2

5
1 1 3 1
1 2 3 4 5

Sample Output #2

12 42 32 52 42

Notes/Hints

Special Constraint A: $\forall 1 \le i \le n, b_i = i$.

For all data: $2 \le n \le 5000$, $1 \le fa_i < i$, $0 \le b_i < 10^9+7$.

见题面 Input 部分

见题面 Output 部分