#include<iostream> #include<cstdio> #include<algorithm> #include<ctype.h> #define int long long using namespace std; 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*10+ch-'0'; ch=getchar(); } return x*f; } const int N=1000005,Mod=1e9+7; int head[N],to[N],nxt[N],cnt; void add(int u,int v) { to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; } int val[N],sz[N],rnd[N],sum[N],tr[2][N],tot,rt; void maintain(int x) { sz[x]=sz[tr[0][x]]+sz[tr[1][x]]+1; sum[x]=sum[tr[0][x]]+sum[tr[1][x]]+val[x]; } int node(int x) { tot++; val[tot]=sum[tot]=x; rnd[tot]=((rand()<<15)|rand()); tr[0][tot]=tr[1][tot]=0; sz[tot]=1; return tot; } void split(int key,int now,int &x,int &y) { if(!now)return x=y=0,void(); if(val[now]<=key) { x=now; split(key,tr[1][now],tr[1][x],y); } else { y=now; split(key,tr[0][now],x,tr[0][y]); } maintain(now); } int merge(int x,int y) { if(!x||!y)return x+y; if(rnd[x]>rnd[y]) { tr[1][x]=merge(tr[1][x],y); maintain(x); return x; } else { tr[0][y]=merge(x,tr[0][y]); maintain(y); return y; } } void ins(int x) { int Le,Rt; split(x,rt,Le,Rt); rt=merge(Le,merge(node(x),Rt)); } void del(int x) { int Le,Rt,awa1,awa2; split(x-1,rt,Le,Rt); split(x,Rt,awa1,awa2); rt=merge(Le,merge(merge(tr[0][awa1],tr[1][awa1]),awa2)); } int query(int x) { int Le,Rt; split(x,rt,Le,Rt); int ret=sum[Rt],szz=sz[Le]; // printf("!!! %lld :: %lld %lld\n",x,ret,szz); rt=merge(Le,Rt); return (ret%Mod+szz%Mod*x%Mod)%Mod; } int n,a[N],ans,cur; void work(int now,int fath) { ins(a[now]); // printf("AWA:: %lld %lld\n",now,a[now]); cur=(cur+query(a[now]))%Mod; ans=(ans+cur)%Mod; for(int i=head[now]; i; i=nxt[i]) { int v=to[i]; if(v==fath) continue; work(v,now); } cur=(cur-query(a[now])+Mod)%Mod; del(a[now]); } int qpow(int base,int t) { int ret=1; while(t) { if(t&1) ret=ret*base%Mod; base=base*base%Mod; t>>=1; } return ret; } signed main() { n=read(); for(int i=1; i<=n; i++) a[i]=read(),ans=(ans+a[i])%Mod; for(int u,v,i=1; i<n; i++) u=read(),v=read(),add(u,v),add(v,u); for(int i=1; i<=n; i++) work(i,0),rt=tot=cur=0; printf("%lld\n",ans*qpow(2,Mod-2)%Mod); return 0; }