描述

一天，有一位顾客来到了星象馆。
看完了演出后，这位顾客找到了梦美：“我看到美丽的星空后，突然想到了一道难题，希望你能帮我解决。”
题目是这样的：有一个星座，每个星星都有一个权值\(V_i\)，一共有\(n-1\)条边把\(n\)个星星连了起来。要你求
\[ \sum^n_{i=1}\sum^n_{j=1}max(V_\text{The path from i to j})-min(V_\text{The path from i to j}) \]
梦美一下子就想到了\(O(n^2)\)的暴力。然而这跑的实在是太慢了。所以她就不得不向你求助了。

输入

第一行一个整数\(n\)。
第二行\(n\)个数，表示每个节点的权值。
接下来\(n-1\)行，每行两个整数\((u,v)\)，表示\(u\)和\(v\)之间有边。

输出

一行一个整数，表示答案，对\(1000000007\)取模。

样例输入

3
1 2 3
1 2
2 3

样例输出

8

数据范围

对于\( 10\% \)的数据，\( n\leq 2000 \)
对于\( 30\% \)的数据，\( n\leq 50000 \)
对于\( 100\% \)的数据，\( n\leq 500000 \)