题目背景

HansBug持续无聊ing

题目描述

由于aaa没有完成HansBug的任务。所以HansBug开始计划着如何续aaa。

现在HansBug手里有 $N$个aaa，每个aaa有一个码力值。一共存在 $N - 1$条连接两个aaa的边，故这 $N$个aaa构成一棵有根树，根为1号aaa。

现在HansBug想要续了这 $N$个aaa。HansBug所采用的策略是，对于第 $i$个aaa，先让他和他的各级子aaa们乖乖♂站好成一队，然后依次续掉。

经过长期对于aaa码力值的研究，HansBug发现，对于每一队aaa，设有 $n$个，码力值依次为$v_i$，则续了队伍里的第 $i$个aaa所能获得的码力值为 $v_1 + v_2 + \cdots + v_i$。

然而，aaa之间的关系树相当的复杂，HansBug的智商早已不够用，于是这个任务就交给了你。不过HansBug知道，任何一个aaa都不会有超过5个的直接子aaa

HansBug想要知道在每次排♂队方法最优的情况下，续了这些aaa最多可以获得的码力值~~，事成之后分给你100000 % 10点码力值~~。

输入格式

第一行包含一个正整数 $N$，表示aaa的个数。

接下来 $N-1$行，每行包含两个正整数 $u, v$，代表第 $u$个aaa和第 $v$个aaa之间存在从属关系（最高级别的aaa编号为 $1$）

最后一行包含 $N$个非负整数，依次代表第 $i$个aaa的码力值。

输出格式

输出包含一个整数，打表HansBug续掉全部的aaa之后最多能获得的码力值。

由于结果较大，所以请对 $1000000007$ 取模 （${10} ^ 9 + 7$）

5
5 3
1 2
1 5
4 5
3 9 10 4 7 

189

提示

样例解释：

故续了5个aaa所得的最大总码力值为：118 + 9 + 10 + 4 + 48 = 189

对1000000007取模后得到答案189

数据范围：

对于30%的数据：$1 \leq N \leq 3 \cdot {10}^3$

对于50%的数据：$1 \leq N \leq 2 \cdot {10}^4$

对于70%的数据：$1 \leq N \leq {10}^5$

对于100%的数据：$1 \leq N \leq 5 \cdot {10}^5$

对于每一个aaa的码力值 $a_i$，保证 $0 \leq a_i \leq {10}^8$