#include <iostream> #include <vector> #include <algorithm> #define ll long long using namespace std; const ll MOD = 1000000007; const int N = 500010; vector<int>G[N]; int a[N],fa[N],dep[N],tmp[N]; void DFS(int x,int father) { fa[x] = father; dep[x] = dep[father] + 1; for(int i(0);i < G[x].size();i++) { int v = G[x][i]; if(v == father) continue; DFS(v,x); } } ll solve(ll x,ll y) { int tot = 0; ll res = 0; if(dep[x] < dep[y]) swap(x,y); while(dep[x] != dep[y]) { tmp[++tot] = a[x]; x = fa[x]; } while(x != y) { tmp[++tot] = a[x]; x = fa[x]; tmp[++tot] = a[y]; y = fa[y]; } tmp[++tot] = a[x]; sort(tmp + 1,tmp + tot + 1); for(int i(1);i <= tot;i++) res = (res + tmp[i] * i % MOD) % MOD; return res; } int main() { int n,i; ll ans = 0; cin>>n; for(i = 1;i <= n;i++) cin>>a[i]; for(i = 1;i < n;i++) { int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } DFS(1,0); for(i = 1;i <= n;i++) for(int j(i);j <= n;j++) ans = (ans + solve(i,j)) % MOD; cout<<ans; return 0; }