Problem Description

Given a rooted tree with $n$ nodes, where node $1$ is the root, let the parent of $u$ be $fa_u$. You are also given a weight sequence $b$ of length $n$.

A permutation $a$ of length $n$ is called a valid topological order of 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}$ over all valid topological orders of this tree.

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

Input Format

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

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

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

Output Format

Output one line with $n$ integers. The $i$-th integer denotes $f(i) \bmod 10^9+7$.

5
1 1 3 2
3 5 4 4 1

18 27 27 15 15 

5
1 1 3 1
1 2 3 4 5

12 42 32 52 42

Hint

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

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

Translated by ChatGPT 5