#include using namespace std; using ll=long long; using vin=vector; using vll=vector; using vvin=vector>; using vvll=vector>; using vstr=vector; using vvstr=vector>; using vch=vector; using vvch=vector>; using vbo=vector; using vvbo=vector>; using vpii=vector>; using pqsin=priority_queue,greater>; #define mp make_pair #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,s,n) for(int i=(s);i<(int)(n);i++) #define all(v) v.begin(),v.end() #define decp(n) cout<>n; vin a(n-1),b(n-1); vin par(n+1,-1); vvin baby(n+1); vbo r(n+1,false); rep(i,n-1){ cin>>a[i]>>b[i]; baby[a[i]].push_back(b[i]); par[b[i]]=a[i]; r[b[i]]=true; } int root; rep(i,n)if(!r[i+1])root=i+1; queue qq;qq.push(root); vin d(n+1);d[root]=1; while(qq.size()){ auto p=qq.front();qq.pop(); if(baby[p].size()==0)continue; for(auto tmp:baby[p]){ d[tmp]=d[p]+1; qq.push(tmp); } } vin child(n+1,1);//the number of children priority_queue> q; rep(i,n)if(baby[i+1].size()==0)q.push(mp(d[i+1],i+1)); while(q.size()){ auto p=q.top();q.pop(); if(par[p.second]==-1)continue; child[par[p.second]]+=child[p.second]; q.push(mp(d[p.second],par[p.second])); } ll ans=(ll)0; rep(i,n-1){ ans+=((ll)d[a[i]]*(ll)child[b[i]])%inf; ans%=inf; } cout<