题目背景

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
5 3
1 2
1 5
4 5
3 9 10 4 7 

189

提示

样例解释

故续了 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$。