aaa被续

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 $