// #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define int long long inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } const int N=100100,P=1000000007; inline int fpow(int a,int b=P-2){ int c=1; for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P; return c; } int L[N<<1],R[N<<1],ls[N<<1],rs[N<<1],ver,rt; inline int New(int L_,int R_,int ls_,int rs_){ L[++ver]=L_,R[ver]=R_,ls[ver]=ls_,rs[ver]=rs_; return ver; } int build(int l,int r){ if(l==r)return New(l,r,0,0); int mid=(l+r)>>1; return New(l,r,build(l,mid),build(mid+1,r)); } class bst{ public: int sum[N<<1],laz[N<<1]; bst(){memset(sum,0,sizeof(sum));memset(laz,0,sizeof(laz));} inline void push_down(int nd){ sum[nd]=(sum[nd]+laz[nd]*(R[nd]-L[nd]+1))%P; laz[ls[nd]]=(laz[ls[nd]]+laz[nd])%P; laz[rs[nd]]=(laz[rs[nd]]+laz[nd])%P; laz[nd]=0; } inline void push_up(int nd){sum[nd]=(sum[ls[nd]]+sum[rs[nd]]);} void add(int l,int r,int k,int nd=rt){ push_down(nd); if(l<=L[nd]&&R[nd]<=r){laz[nd]=(laz[nd]+k)%P;return;} if(l<=R[ls[nd]])add(l,r,k,ls[nd]),push_down(ls[nd]); if(r>=L[rs[nd]])add(l,r,k,rs[nd]),push_down(rs[nd]); push_up(nd); } int get_sum(int l,int r,int nd=rt){ push_down(nd); if(l<=L[nd]&&R[nd]<=r)return sum[nd]; int res=0; if(l<=R[ls[nd]])res=(res+get_sum(l,r,ls[nd]))%P; if(r>=L[rs[nd]])res=(res+get_sum(l,r,rs[nd]))%P; return res; } }ds1,ds2; int n,head[N],to[N<<1],nex[N<<1],l[N],r[N],prd=1; int siz[N]; bool vis[N]; int ans=0; void init(){ cin>>n; for(int i=1;i<=n;i++)l[i]=read(),r[i]=read(),prd=prd*(r[i]-l[i]+1)%P; for(int i=1;i<n;i++){ int u=read(),v=read(); to[i<<1]=v; nex[i<<1]=head[u]; head[u]=i<<1; to[i<<1|1]=u; nex[i<<1|1]=head[v]; head[v]=i<<1|1; } rt=build(1,1e5); } int get_siz(int nd,int fa){ siz[nd]=1; for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]&&to[i]!=fa)siz[nd]+=get_siz(to[i],nd); return siz[nd]; } int barycenter(int nd,int tot,int fa){ int mx=tot-siz[nd]; for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]&&to[i]!=fa)mx=max(mx,siz[to[i]]); if(mx*2<=tot)return nd; for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]&&to[i]!=fa){ int x=barycenter(to[i],tot,nd); if(x)return x; } return 0; } void calc(int nd,int dis,int fa){ ans=(ans+(ds1.get_sum(l[nd],r[nd])*dis+ds2.get_sum(l[nd],r[nd]))%P*prd%P*fpow(r[nd]-l[nd]+1))%P; for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]&&to[i]!=fa)calc(to[i],dis+1,nd); } void add(int nd,int dis,int fa){ ds1.add(l[nd],r[nd],fpow(r[nd]-l[nd]+1)); ds2.add(l[nd],r[nd],dis*fpow(r[nd]-l[nd]+1)%P); for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]&&to[i]!=fa)add(to[i],dis+1,nd); } void clear(int nd,int dis,int fa){ ds1.add(l[nd],r[nd],-fpow(r[nd]-l[nd]+1)); ds2.add(l[nd],r[nd],-dis*fpow(r[nd]-l[nd]+1)%P); for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]&&to[i]!=fa)clear(to[i],dis+1,nd); } void solve(int nd){ nd=barycenter(nd,get_siz(nd,0),0); vis[nd]=true; ds1.add(l[nd],r[nd],fpow(r[nd]-l[nd]+1)); for(int i=head[nd];i;i=nex[i])if(!vis[to[i]]){ calc(to[i],1,nd); add(to[i],1,nd); } clear(nd,0,0); for(int i=head[nd];i;i=nex[i])if(!vis[to[i]])solve(to[i]); } signed main(){ // freopen("route.in","r",stdin); // freopen("route.out","w",stdout); init(); solve(1); cout<<(ans+P)%P; return 0; }