#include <bits/stdc++.h> #include<set> using namespace std; const int N=5e5+5; const long long Mod=1e9+7; int n,root=1; int A[N]; set<long long>S; inline int Read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } int Head[N],To[N*2],Nxt[N*2],E; void Addedge(int x,int y) { To[++E]=y; Nxt[E]=Head[x]; Head[x]=E; } int F[N][21]; int Dep[N]; void DFS(int u,int fa) { F[u][0]=fa; Dep[u]=Dep[fa]+1; for(int i=1; i<=20; i++) F[u][i]=F[F[u][i-1]][i-1]; int v; for(int i=Head[u]; i; i=Nxt[i]) if((v=To[i])!=fa) DFS(v,u); } int LCA(int u,int v) { if(Dep[u]<Dep[v]) swap(u,v); for(int i=20; i>=0; i--) { while(Dep[F[u][i]]>=Dep[v]) u=F[u][i]; } if(u==v) return v; for(int i=20; i>=0; i--) while(F[u][i]!=F[v][i]) u=F[u][i],v=F[v][i]; return F[u][0]; } long long ans=0; long long Cal(int x,int y) { S.clear(); int z=LCA(x,y); S.insert(A[z]); while(x!=z) { S.insert(A[x]); x=F[x][0]; } while(y!=z) { S.insert(A[y]); y=F[y][0]; } long long ans=0; long long j; set<long long>::iterator it; for(it=S.begin(),j=1; it!=S.end(); it++,j++) ans=(ans+(*it)*j)%Mod; return ans; } int main() { n=Read(); for(int i=1; i<=n; i++) A[i]=Read(); for(int i=1; i<n; i++) { int x=Read(),y=Read(); Addedge(x,y); Addedge(y,x); } DFS(root,0); for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) ans=(ans+Cal(i,j))%Mod; printf("%lld",ans); return 0; }