Given a rooted tree with $n$ nodes, where $1$ is the root and $fa_u$ denotes the parent of $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.

For each $1 \le u \le n$, calculate $f(u) \bmod 10^9+7$.

Input

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

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

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

Output

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

Examples

Input 1

5
1 1 3 2 
3 5 4 4 1

Output 1

18 27 27 15 15

Input 2

5
1 1 3 1
1 2 3 4 5

Output 2

12 42 32 52 42

Subtasks

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$.