#include<bits/stdc++.h> using namespace std; const int N=1e6+10,mod=1e9+7; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} int n,ans[N]; int delta[N][2],op[N]; int delta2[N][2]; int ch[N][2],fa[N]; int f[N],g[N]; bool chk(int x){ return ch[fa[x]][1]==x; } int b[N][2],dep[N]; void dfs1(int u){ int f=u;if(fa[f]) f=fa[f];if(fa[f]) f=fa[f]; Add(delta[u][0],delta[f][0]); Add(delta[u][1],delta[f][1]); b[u][0]=1; if(ch[u][0]){ dep[ch[u][0]]=dep[u]+1; dfs1(ch[u][0]); b[u][0]+=b[ch[u][0]][1]; b[u][1]+=b[ch[u][0]][0]; } if(ch[u][1]){ dep[ch[u][1]]=dep[u]+1; dfs1(ch[u][1]); b[u][0]+=b[ch[u][1]][1]; b[u][1]+=b[ch[u][1]][0]; } }void dfs2(int u){ if(ch[u][0]){ Add(f[ch[u][0]],f[u]); dfs2(ch[u][0]); } if(ch[u][1]){ Add(f[ch[u][1]],f[u]); dfs2(ch[u][1]); } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>ch[i][0]>>ch[i][1]; fa[ch[i][0]]=i; fa[ch[i][1]]=i; }for(int i=1;i<=n;i++){ if(fa[i]){ if(!fa[fa[i]]){//Zig delta[i][chk(i)]=mod-1;op[i]=1; }else if(chk(i)==chk(fa[i])){//Zig-Zig delta[i][0]=mod-1;delta[i][1]=mod-1; delta[i][chk(i)]--;op[i]=2; }else{//Zig-Zag delta[i][0]=mod-1;delta[i][1]=mod-1; op[i]=3; } } }dfs1(1); for(int i=1;i<=n;i++){ if(ch[i][0]) Add(f[ch[i][0]],1ll*delta[i][0]%mod); if(ch[i][1]) Add(f[ch[i][1]],1ll*delta[i][1]%mod); //y=fa(x) Add(g[i],mod-dep[i]); //y=x for(int o1=0;o1<=1;o1++){ for(int o2=0;o2<=1;o2++){ int x=ch[ch[i][o1]][o2]; if(!x) continue; if(o1==o2) Add(g[i],2ll*b[x][0]%mod); else Add(g[i],b[x][0]); //if(i==6)cout<<b[x][0]*((o1==o2)+1)<<endl; Add(g[i],1ll*delta[i][o1^1]*b[x][0]%mod); } int x=ch[i][o1]; if(!x) continue; if(op[x]==1) Add(g[i],b[x][0]); else if(op[x]==2) Add(g[i],1ll*b[x][0]*delta[fa[i]][chk(i)^1]%mod); else if(op[x]==3) Add(g[i],1ll*b[x][0]*delta[fa[i]][chk(i)]%mod); } //y\in subtree(x) if(!fa[i]) continue; int br=ch[fa[i]][chk(i)^1]; if(op[br]!=3) Add(f[i],b[br][0]); if(fa[fa[i]]){ int fth=fa[fa[i]],o=(op[br]==2); Add(f[i],1ll*b[br][0]*delta[fth][chk(fa[i])^o]); } if(ch[br][0]){ if(op[ch[br][0]]==3) Add(f[i],b[ch[br][0]][0]); else Add(f[i],2ll*b[ch[br][0]][0]%mod); } if(ch[br][1]){ if(op[ch[br][1]]==3) Add(f[i],b[ch[br][1]][0]); else Add(f[i],2ll*b[ch[br][1]][0]%mod); } Add(f[i],1ll*delta[fa[i]][chk(i)]*b[br][1]%mod); }dfs2(1); //for(int i=1;i<=n;i++) cout<<f[i]<<' '<<g[i]<<endl; for(int i=1;i<=n;i++){ cout<<(1ll*dep[i]*n+f[i]+g[i])%mod<<'\n'; }cout.flush(); return 0; } /* #include<bits/stdc++.h> using namespace std; const int N=1e6+10,mod=1e9+7; int n,par[N],ans[N]; struct node{ int ch[2],fa; }t[N],t0[N]; #define fa(x) t[x].fa #define ch(x,id) t[x].ch[id] bool chk(int x){ return (x==ch(fa(x),1)); } void rotate(int x){ //cout<<x<<endl;for(int i=1;i<=n;i++) cout<<ch(i,0)<<' '<<ch(i,1)<<endl;cout<<endl; int f=fa(x),f2=fa(f); if(!f) return ; int id=chk(x); ch(f,id)=ch(x,id^1); fa(ch(x,id^1))=f; if(f2) ch(f2,chk(f))=x;fa(x)=f2; ch(x,id^1)=f;fa(f)=x; //for(int i=1;i<=n;i++) cout<<ch(i,0)<<' '<<ch(i,1)<<endl;cout<<endl; } void splay(int x){ for(;fa(x);rotate(x)){ if(fa(fa(x))){ if(chk(x)==chk(fa(x))) rotate(fa(x)); else rotate(x); } } } int dep[N]; void dfs(int u){ if(!u) return ; dep[u]=dep[fa(u)]+1; dfs(ch(u,0));dfs(ch(u,1)); } void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} int main(){ freopen("dream.in","r",stdin); freopen("dream.out","w",stdout); cin>>n; for(int i=1;i<=n;i++){ int a,b;cin>>a>>b; t0[i].ch[0]=a,t0[i].ch[1]=b; par[a]=i,par[b]=i; }for(int i=1;i<=n;i++){ t0[i].fa=par[i]; }for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) t[j]=t0[j]; splay(i);dfs(i); for(int j=1;j<=n;j++) Add(ans[j],dep[j]-1),cout<<i<<' '<<j<<' '<<dep[j]-1<<endl; }for(int i=1;i<=n;i++) cout<<ans[i]<<endl; return 0; } */