#include<bits/stdc++.h> #define upf(i,n,k) for(int i=k;i<=n;i++) #define lowf(i,n,k) for(int i=n;i>=k;i--) #define Max(a,b,c) max(a,max(b,c)) #define Min(a,b,c) min(a,min(b,c)) #define ofile(N) freopen(N".in","r",stdin),freopen(N".out","w",stdout) #define ri register int #define ie inline #define ll long long using namespace std; struct edge { int u,v,next,val; } e[1000010]; int n,tot; const int mod=1e9+7; int ans,head[1000011],vis[1000011],tmp[1000010]; void ins(int u,int v) { e[tot++].u=u; e[tot].v=v; e[tot].next=head[u]; head[u]=tot; } ie int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } ie void out(int a) { if(a>=10)out(a/10); putchar(a%10+'0'); } ie void dfs(int u,int r,int cnt) { if(r==u) { memset(tmp,0,sizeof(tmp)); tmp[1]=e[r].val; } if(u>r) { sort(tmp+1,tmp+cnt+1); upf(i,cnt,1)ans+=i*tmp[i]; ans%=mod; } vis[u]=1; for(int i=head[u]; i; i=e[i].next) { int v=e[i].v; if(!vis[v]) { vis[v]=1; tmp[cnt+1]=e[v].val; dfs(v,r,cnt+1); } } vis[u]=0; } int main() { //ofile(""); n=read(); upf(i,n,1)e[i].val=read(),ans+=e[i].val; upf(i,n-1,1) { int u=read(),v=read(); ins(u,v); ins(v,u); } upf(i,n,1) { dfs(i,i,1); // cnt=0; } cout<<ans%mod; return 0; }