小F的圣诞树
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

圣诞树上挂有 n 个礼物，每个礼物的编号分别为 1 到 n。为了方便描述，将每个礼物描述成
一个节点，由 n-1 条无向边将这些节点连接起来，形成一个连通图。

1 号节点作为树的根节点，每个礼物有一个重量，第 i 个礼物的重量为 w_i。定义树上每个节点的深度为该节点到根节点的最短路径所经过的边数，根节点的深度为 0。

已知树上任意两个礼物之间的相互作用为它们的重量最大值乘以它们的深度之和，请求出树上任意两个礼物之间的相互作用之和有多大。

由于答案较大，请输出对取模的结果。

输入描述:

第一行一个整数 ，表示礼物的个数。
接下来一行 n 个整数，其中第 i 个整数表示，编号为 i 的礼物重量 。
最后 n-1 行，每行两个整数 ，表示节点 u 与节点 v 之间有一条无向边。

输出描述:

一行一个整数，表示答案。
示例1

输入

复制 
3
1 2 3
1 2
1 3

输出

复制 
11
示例2

输入

复制 
6
1 1 4 5 1 4
1 2
1 3
2 4
2 5
3 6

输出

复制 
158