#include<cstdio> #include<algorithm> #define rep(a,b,c) for(int c(a);c<=(b);++c) #define grep(b,c) for(int c(head[b]);c;c=nxt[c]) inline int read() { int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar(); while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res; } const int N=5e5+10,Mod=1e9+7;int head[N],des[N<<1],nxt[N<<1],cgt; inline void ins(int x,int y) { nxt[++cgt]=head[x];des[head[x]=cgt]=y; nxt[++cgt]=head[y];des[head[y]=cgt]=x; } typedef long long LL;int n,a[N],P[N],p; inline int bnd(int k){int l(1),r(p),m;while(l<=r)P[m=(l+r)>>1]<=k?l=m+1:r=m-1;return l-1;} namespace Sub0 { const int N=2010;int s[N];LL ans,t[N];bool vis[N][N]; inline void add(int x) { int w=P[x];x=p-x+1; while(x<=p)t[x]+=w,++s[x],x+=(x&-x); } inline void del(int x) { int w=P[x];x=p-x+1; while(x<=p)t[x]-=w,--s[x],x+=(x&-x); } struct Pair{LL t;int s;}; inline Pair qry(int x) { Pair res;res.t=res.s=0;x=p-x+1; while(x)res.t+=t[x],res.s+=s[x],x^=(x&-x);return res; } int RT;inline void dfs(int u,LL res=0,int dep=1,int fa=0) { Pair r=qry(a[u]);res+=1ll*P[a[u]]*(dep-r.s)+r.t;add(a[u]); if(!vis[RT][u]){ans+=res;vis[RT][u]=vis[u][RT]=true;} grep(u,i)if(des[i]!=fa)dfs(des[i],res,dep+1,u);del(a[u]); } inline void mian(){rep(1,n,i){dfs(RT=i);ans%=Mod;}printf("%lld\n",ans);return;} } int main() { n=read();rep(1,n,i)P[i]=a[i]=read();rep(2,n,i)ins(read(),read()); std::sort(P+1,P+n+1);p=std::unique(P+1,P+n+1)-P-1;rep(1,n,i)a[i]=bnd(a[i]); if(n<=2000)return Sub0::mian(),0; }