#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=5e5+10; const ll mod=1e9+7; int n; int a[N]; struct edge{ int nxt,go; }e[N*2]; int head[N],cnt; void adde(int u,int v){e[++cnt]=(edge){head[u],v},head[u]=cnt;} struct tr{ int ls,rs; ll num,sum; }t[N*20]; int rt,tot; ll ans[N],rans; void add(int &k,int l,int r,int pos,int val) { if(!k) k=++tot; t[k].num+=1ll*val,t[k].sum+=1ll*pos*val; t[k].sum%=mod; if(pos==l&&l==r) return ; int mid=(l+r)>>1; if(pos<=mid) add(t[k].ls,l,mid,pos,val); else add(t[k].rs,mid+1,r,pos,val); } ll querynum(int k,int l,int r,int x,int y) { if(!k) return 0; if(x<=l&&r<=y) return t[k].num; int mid=(l+r)>>1; ll ret=0; if(x<=mid) ret+=querynum(t[k].ls,l,mid,x,y),ret%=mod; if(y>mid) ret+=querynum(t[k].rs,mid+1,r,x,y),ret%=mod; return ret; } ll querysum(int k,int l,int r,int x,int y) { if(!k) return 0; if(x<=l&&r<=y) return t[k].sum; int mid=(l+r)>>1; ll ret=0; if(x<=mid) ret+=querysum(t[k].ls,l,mid,x,y),ret%=mod; if(y>mid) ret+=querysum(t[k].rs,mid+1,r,x,y),ret%=mod; return ret; } int maxn; void dfs(int u,int f) { ans[u]=((ans[f]+querysum(1,1,maxn,a[u],maxn))+((querynum(1,1,maxn,1,a[u]-1)+1)*a[u]))%mod; add(rt,1,maxn,a[u],1); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].go; if(v!=f) dfs(v,u); } add(rt,1,maxn,a[u],-1); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),maxn=max(maxn,a[i]); for(int i=1;i<n;i++) { int u,v; scanf("%d %d",&u,&v); adde(u,v),adde(v,u); } for(int i=1;i<=n;i++) { dfs(i,0); for(int j=1;j<=n;j++) if(j!=i) rans=(rans+ans[j])%mod; } rans/=2; for(int i=1;i<=n;i++) rans+=1ll*a[i]; printf("%lld\n",rans); return 0; }