题目背景

小Z和小H发明了一个新游戏。

题目描述

游戏在树上进行，每个点有点权。

每次他们会选两个点 $s,t$，并将一个棋子放在点 $s$ 上。

他们会轮流移动棋子，到过的点不能再走，并且他们会保证最后移到 $t$ 上。

小Z先手，分数一开始为 $a_s$。

若当前是小Z移动的，分数就减去到达点的点权，否则就加上到达点的点权。

小Z想要答案尽可能小，小H会让答案尽可能地大。

设最后的分数是 $f_{s,t}$。

求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{i,j}$。

输入格式

第一行一个数 $n$，表示树的点数。

第二行 $n$ 个数，$a_i$ 表示第 $i$ 个点的点权。

接下来 $n-1$ 行，每行两个数 $x,y$ 表示 $x$ 到 $y$ 之间有一条边。

输出格式

一个数表示 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{i,j}$。

对 $10^9+7$ 取模。

4
-4 1 5 -2
1 2
1 3
1 4

40

8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8

4

提示

数据保证 $2\le n \le 2\times 10^5,-10^9\le a_i \le10^9$。