#include<bits/stdc++.h> using namespace std; const int N=2e5+10,mod=1e9+7; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} void Sub(int &a,int b){a-=b;if(a<0) a+=mod;} void Mul(int &a,int b){a=1ll*a*b%mod;} vector<int> E[N]; int hi[N],h[N],bel[N],top[N],dep[N],csz[N],cc=0; vector<int> f[N],tag[N]; int n; void dfs1(int u,int fa){ dep[u]=dep[fa]+1; hi[u]=0; for(auto v:E[u]){ if(v==fa) continue; dfs1(v,u); hi[u]=max(hi[u],hi[v]+1); }h[u]=0; for(auto v:E[u]){ if(v==fa) continue; if(hi[v]+1==hi[u]) h[u]=v; } } void dfs2(int u,int fa,int tp){ if(tp==u){ bel[u]=++cc; csz[bel[u]]=hi[u]+1; f[bel[u]].resize(hi[u]+5); tag[bel[u]].resize(hi[u]+5); for(int i=0;i<=hi[u]+2;i++) f[bel[u]][i]=0; for(int i=0;i<=hi[u]+2;i++) tag[bel[u]][i]=1; }else{ bel[u]=bel[fa]; } top[u]=tp; if(h[u]) dfs2(h[u],u,tp); for(auto v:E[u]){ if(v==fa||v==h[u]) continue; dfs2(v,u,v); } } void pdtag(int id){ int tg=1; for(int i=0;i<=csz[id];i++){ Mul(tg,tag[id][i]); Mul(f[id][i],tg); tag[id][i]=1; } } int ans=0; int res[N],rtg[N]; void dfs3(int u,int fa){ for(auto v:E[u]){ if(v==fa) continue; dfs3(v,u); //if(v!=h[u]) pdtag(bel[v]); pdtag(bel[u]); //if(f[bel[v]].size()<=21){ /*cout<<u<<' '<<v<<' '<<bel[v]<<' '<<bel[u]<<endl; for(auto ed:f[bel[v]]) cout<<ed<<' ';cout<<endl; for(auto ed:f[bel[u]]) cout<<ed<<' ';cout<<endl; cout<<endl;*/ //} } int d=dep[u]-dep[top[u]]; int id=bel[u];f[id][d]=1; for(auto v:E[u]){ if(v==fa||v==h[u]) continue; int sumv=0; for(int i=d;i<=csz[bel[v]]+d;i++){ Mul(f[id][i],tag[id][i]); Mul(tag[id][i+1],tag[id][i]); tag[id][i]=1; if(u==1){ Mul(res[i],rtg[i]); Mul(rtg[i+1],rtg[i]); rtg[i]=1; } } /*for(int i=0;i<=hi[v];i++){ tag[id][i+d+1]=f[bel[v]][i]%mod; Add(sumv,f[bel[v]][i]); }if(u==1) Mul(ans,sumv);*/ int sumf=0; for(int i=0;i<=hi[v];i++){ //Mul(tag[id][i+1+d],(sumv+1)%mod); //if(tag[id][i+1+d]!=1) // cout<<u<<' '<<d<<' '<<i+1+d<<' '<<i+csz[bel[v]]<<' '<<i<<' '<<hi[v]<<' '<<sumv<<' '<<tag[id][i+1+d]<<endl; int ad=1ll*(sumf+1)*f[bel[v]][i]%mod; Add(sumf,f[id][i+1+d]); if(u==1) Mul(res[i+1+d],(sumv+1)%mod);//cout<<res[i+1+d]<<' '<<sumv<<endl; if(u==1) Add(res[i+1+d],1ll*f[bel[v]][i]*f[id][i+1+d]%mod);//cout<<f[id][i+1+d]<<' '<<sumv<<endl; Add(sumv,f[bel[v]][i]); tag[id][i+1+d]=(sumv+1)%mod; Mul(f[id][i+1+d],tag[id][i+1+d]); Mul(tag[id][i+2+d],tag[id][i+1+d]); tag[id][i+1+d]=1; Add(f[id][i+1+d],ad); }Mul(rtg[hi[v]+2+d],(sumv+1)%mod); //if(u==1) Mul(ans,sumv); } } void slv(){ cin>>n; for(int i=1;i<=n;i++) E[i].clear(),f[i].clear(),tag[i].clear(); for(int i=1;i<n;i++){ int u,v;cin>>u>>v; E[u].push_back(v); E[v].push_back(u); }dfs1(1,0);cc=0; //sort(E[1].begin(),E[1].end(), //[](int a,int b){return hi[a]>hi[b];}); for(int i=0;i<=n;i++) res[i]=0,rtg[i]=1;ans=0; dfs2(1,0,1); dfs3(1,0); for(int i=0;i<=n;i++){ Mul(res[i],rtg[i]);Mul(rtg[i+1],rtg[i]); Add(ans,res[i]);//,cout<<res[i]<<' '; }//cout<<endl; Add(ans,1);//1 only //cout<<f[1][0]<<' '<<f[1][1]<<' '<<f[1][2]<<' '<<f[1][3]<<' '<<f[1][4]<<endl; cout<<ans<<endl; } int main(){ int t;cin>>t; for(int i=1;i<=t;i++){ cout<<"Case #"<<i<<": "; slv(); } return 0; }