You are given a rooted tree (rooted at 1) with N nodes. Each node has some value associated with it. Let $P_i$ denote the number of paths from node i to a leaf node.

For each of the $P_i$ paths, calculate the product of node values on the path. For each node i, you need to find the sum of these products.

Input:

First line of input contains an integer N. Each of the next $N-1$ lines contains 2 integers A and B, meaning that there is an edge between A and B. Next line contains N space separated integers denoting the node values.

Output:

Print a line with N space separated integers, each of which is the required sum modulo $10^9+7$.

Constraints:

$1 \le N \le 10^6$

$1 \le A, B \le N$

$0 \le$ node values $\le 10^9$