9999012 - 树上排序

小谢喜欢吃树上的水果。不同于常人，小谢每次吃水果前，会沿着树上的一条路径收集经过的节点上的 所有水果，之后他会对收集到的所有水果按美味值从小到大进行排序。对于一个长度为 n 的路径，设小谢讲 所有水果按美味值排序后得到的数组为 {ai}(i = 1 ∼ n)，那么他这次收集水果得到的开心值为 ∑n i=1 i · ai。题 目保证树上每个节点有且只有一个水果，所有水果的美味值两两不同；并且从 u 到 v 的路径与从 v 到 u 的 路径会被为同一条路径。 由于树上的路径树太多了，小谢一时无法决定要按哪条路径去收集水果。他想请你帮他计算所有路径对 应的开心值的和，由于答案可能很大，你需要对 109 + 7 取模后输出。

第一行一个整数 n，表示树的节点数量。 第二行 n 个整数 ai，表示树上每个节点的水果的美味值。 接下来 n − 1 行每行两个整数 ui , vi，表示树上有一条 ui 与 vi 的连边。

共一行，一个非负整数表示答案对 109 + 7 取模的结果。