P3925 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 之后最多能获得的码力值。 **由于结果较大，所以请对 $\bm{1000000007}$（$\bm{{10} ^ 9 + 7}$）取模。**

### 样例解释  故续了 5 个 aaa 所得的最大总码力值为：$118 + 9 + 10 + 4 + 48 = 189$。 **对 $\bm{1000000007}$ 取模后得到答案 $\bm{189 }$。** ### 数据范围 对于 $30\%$ 的数据：$1 \leq N \leq 3 \times {10}^3$； 对于 $50\%$ 的数据：$1 \leq N \leq 2 \times {10}^4$； 对于 $70\%$ 的数据：$1 \leq N \leq {10}^5$； 对于 $100\%$ 的数据：$1 \leq N \leq 5 \times {10}^5$。 对于每一个 aaa 的码力值 $a_i$，保证 $0 \leq a_i \leq {10}^8$。