题目描述

国庆长假，牛牛准备去旅游。牛牛所在的景区有 $N$ 个景点，景点和景点之间一共有 $N − 1$ 条线路相连，同时，每个景点还有一个优美程度 $val_i$。

对于树上的一条游览路线，牛牛用它的两个端点 $s,t$ 来表示，牛牛以 $s$ 为起点，$t$ 为终点。在树上沿最短路线移动。

我们定义 $\text{happy}(s, t)$ 为牛牛在一条游览路线游玩时获得的快乐度。

牛牛每移动一条道路，他的快乐度就会下降 $1$，牛牛将选择这条游览路线中优美程度最大的景点观赏，这将使得他的快乐度上升 $val_{\max}$，其中 $val_{\max}$ 表示游览路线中优美程度最大景点的优美程度。

现在牛牛想要知道给定景点的树结构，以及优美程度的情况下，对于所有端点 $s\not=t$ 时的 $\text{happy}(s,t)$ 之和是多少。

具体来讲，你要求出 $\displaystyle\sum_{s\not= t}\text{happy}(s, t)$ 的值，由于这个数字很大，请输出结果对 $10^9+7$ 取模后的结果。

对于连接景点树结构上的一条边，在输入时用点对 $(u, v)$ 表示景点树结构中节点 $u$ 和节点 $v$ 是直接相连的。

当然了，由于本题的最终答案有可能是一个负数，为了避免这个问题，要求你要输出一个模系负数，即你需要保证最终结果在 $[0,10^9+7)$ 的范围内，如果答案小 $0$，则需要对 $10^9+7$ 取余数后再加上 $10^9+7$ ，例子见样例三。

输入格式

第一行输入一个正整数 $N$，表示景点的数目。

接下来一行输入 $N$ 个非负整数 $val_i$，表示每个景点的优美程度。

接下来 $N−1$ 行，每行两个正整数 $u, v$，表示景区树结构上的一条边。

输出格式

仅一行，表示 $\displaystyle \sum_{s\not=t} \text{happy}(s,t)$ 对 $10^9+7$ 取模的结果。

样例

4
1 5 1 1
1 2
2 3
2 4

42

2
1 1
1 2

0

3
0 0 0
1 2
2 3

999999999

最终的答案为 $−8$，$-8\equiv999999999\pmod{10^9+7}$。

见附加文件中的 b.in

见附加文件中的 b.out

数据范围

• 对于前 $30\%$ 的测试数据，保证 $N\le 10^3$。
• 对于另 $10\%$ 的测试数据，保证景区构成的树结构退化成一条单链。
• 对于另 $10\%$ 的测试数据，保证所有景点的优美程度 $val_i$ 都相同。
• 对于 $100\%$ 的测试数据，保证 $2\le N\le 10^6$，$1\le u,v\le N$，$0\le val_i<10^9+7$。