#include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> #include<iostream> #include<vector> #include<queue> #include<ctime> #include<cmath> #include<queue> #include<map> #include<set> #include<unordered_map> #include<stack> #define pr pair<int,int> #define eps 1e-8 #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 a[N],b[N],n; int dfsn[N],rk[N],sz[N],tp[N],p[N],son[N],fa[N],dep[N],dfscnt; int ans; int tr[2][N]; void modify(int ty,int x,int k) { for(;x<=n;x+=x&-x) tr[ty][x]+=k; } int query(int ty,int x) { int ret=0; for(;x;x-=x&-x) ret+=tr[ty][x]; return ret; } void dfs1(int now,int fath) { sz[now]=1;dep[now]=dep[fath]+1; fa[now]=fath; for(int i=head[now];i;i=nxt[i]) { int v=to[i]; if(v==fath) continue; dfs1(v,now); sz[now]+=sz[v]; if(sz[v]>sz[son[now]]) son[now]=v; } } void dfs2(int now,int t) { tp[now]=t;dfsn[now]=++dfscnt; rk[dfscnt]=now; if(!son[now]) return; dfs2(son[now],t); for(int i=head[now];i;i=nxt[i]) { int v=to[i]; if(v==son[now]||v==fa[now]) continue; dfs2(v,v); } } void work(int now,int fath) { int qwq=query(1,a[now]); ans=(ans+qwq*sz[now]%Mod*b[a[now]]%Mod)%Mod; // printf("awa:: %lld %lld\n",now,qwq); int cntt=0; for(int i=head[now];i;i=nxt[i]) { int v=to[i]; if(v==fath) continue; ans=(ans+cntt*sz[v]%Mod*b[a[now]]%Mod)%Mod; cntt+=sz[v]; modify(1,a[now],n-sz[v]); work(v,now); modify(1,a[now],-(n-sz[v])); } } int querylink(int x,int y) { if(!x||!y) return 0; int ret=0; while(tp[x]!=tp[y]) { if(dep[tp[x]]<dep[tp[y]]) swap(x,y); ret+=query(0,dfsn[x])-query(0,dfsn[tp[x]]-1); x=fa[tp[x]]; } ret+=dep[x]>dep[y]?query(0,dfsn[x])-query(0,dfsn[y]-1):query(0,dfsn[y])-query(0,dfsn[x]-1); return ret; } signed main() { n=read(); for(int i=1;i<=n;i++) b[i]=a[i]=read(),p[i]=i; sort(b+1,b+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b; for(int i=1;i<n;i++) { int u=read(),v=read(); add(u,v);add(v,u); } dfs1(1,0);dfs2(1,1); work(1,0); //printf("??? %lld\n",ans); sort(p+1,p+n+1,[&](int x,int y){return a[x]<a[y];}); for(int i=1;i<=n;i++) { modify(0,dfsn[p[i]],sz[p[i]]); int qwq=query(0,dfsn[p[i]]+sz[p[i]]-1)-query(0,dfsn[p[i]]-1); // printf("ovo :: %lld ",qwq); ans=(ans+b[a[p[i]]]*qwq%Mod*(n-sz[p[i]]+1)%Mod)%Mod; qwq=query(0,n)-qwq-querylink(1,fa[p[i]]); // printf("%lld\n",qwq); ans=(ans+b[a[p[i]]]*qwq%Mod*sz[p[i]]%Mod)%Mod; } printf("%lld\n",ans); return 0; }