#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int maxn=5e5+5; int n,a[maxn],ans,dep[maxn],f[maxn][25]; vector<int> adj[maxn]; void dfs(int u,int p) { dep[u]=dep[p]+1; f[u][0]=p; for(int i=1;i<=22;++i) f[u][i] = f[f[u][i-1]][i-1]; for(int i=0;i<adj[u].size();++i) { int v=adj[u][i]; if(v == p) continue; dfs(v,u); } } int lca(int u,int v) { if(dep[u] < dep[v]) swap(u,v); for(int i=22;i>=0;--i) { if(dep[f[u][i]] >= dep[v]) u=f[u][i]; } if(u==v) return u; for(int i=22;i>=0;--i) { if(f[u][i] != f[v][i]) { u=f[u][i]; v=f[v][i]; } } return f[u][0]; } int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<n;++i) { int u,v; scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } dfs(1,1); for(int i=1;i<=n;++i) { for(int j=i;j<=n;++j) { int clk=0; int g[maxn]; int ca=lca(i,j); g[++clk] = a[ca]; int u=i,v=j; while(u!=ca) { g[++clk] = a[u]; u=f[u][0]; } while(v!=ca) { g[++clk] = a[v]; v=f[v][0]; } sort(g+1,g+1+clk); for(int i=1;i<=clk;++i) { //cout<<g[i]<<endl; ans=(ans+(i*g[i])%mod)%mod; } } } printf("%d",ans); }