#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } inline int add(int a,int b){if((a+=b)>=mod)a-=mod;return a;} inline int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } int n; vector<int>E[maxn]; int ans[maxn]; struct _vector { vector<int>v; void push(int x){v.p_b(x);} void upd(int p,int k){ if(p>=v.size())return; p=v.size()-1-p; v[p]=v[p]*1ll*k%mod; } void updv(int p,int k){ if(p>=v.size())return; p=v.size()-1-p; v[p]=k; } int g(int p){ if(p>=v.size())return 0; return v[v.size()-1-p]; } }; #define SW(a,b) a.v.swap(b.v) struct _array { _vector v1,v2; void get_val(int lim){ int prod=1; up(i,0,lim)prod=prod*1ll*v2.g(i)%mod,v1.upd(i,prod),v2.updv(i,1); if(lim+1<v2.v.size())v2.upd(lim+1,prod); } }F[maxn],tmp[maxn]; void conv(_array &a,_array b){ int len=b.v1.v.size()-1; b.get_val(len);a.get_val(len); vector<int>s1(len+1,0),s2(len+1,0); up(i,0,len){ if(i)s1[i]=s1[i-1],s2[i]=s2[i-1]; s1[i]=add(s1[i],b.v1.g(i)); s2[i]=add(s2[i],a.v1.g(i)); } up(i,0,len){ int k=s1[i]*1ll*s2[i]%mod; if(i)k=add(k,mod-s1[i-1]*1ll*s2[i-1]%mod); a.v1.updv(i,k); } a.v2.upd(len+1,s1.back()); } void dfs(int u,int fa){ if(E[u].size()==1&&fa){ F[u].v1.push(1),F[u].v2.push(1); if(fa==1)tmp[u]=F[u]; F[u].v1.push(1),F[u].v2.push(1); return; }int p=0; for(int x:E[u])if(x!=fa){ dfs(x,u); if(!p)p=x; else if(F[x].v1.v.size()>F[p].v1.v.size())p=x; } SW(F[u].v1,F[p].v1); SW(F[u].v2,F[p].v2); for(int x:E[u])if(x!=fa&&x!=p)conv(F[u],F[x]); if(fa==1)tmp[u]=F[u],tmp[u].get_val(tmp[u].v1.v.size()-1); if(u!=1)F[u].v1.push(1),F[u].v2.push(1); } void dfs2(int u,int fa){ ans[u]=1; for(int x:E[u])if(x!=fa)dfs2(x,u),ans[u]=ans[u]*1ll*(ans[x]+1)%mod; } void slv(){ n=read();up(i,1,n)E[i].clear(),F[i].v1.v.clear(),F[i].v2.v.clear(); up(i,1,n-1){ int x=read(),y=read(); E[x].p_b(y),E[y].p_b(x); }dfs(1,0); int SZ=F[1].v1.v.size(); F[1].get_val(F[1].v1.v.size()-1); vector<int>vec(SZ); up(i,0,SZ-1)vec[i]=F[1].v1.g(i); up(i,1,SZ-1)vec[i]=add(vec[i],vec[i-1]); int res=0; for(int x:E[1]){ int S=1; up(i,0,(int)tmp[x].v1.v.size()-1){ int prod=tmp[x].v1.g(i); prod=prod*1ll*vec[i]%mod; //cout<<"Test "<<vec[i]<<" "<<S<<endl; prod=prod*1ll*qp(S,mod-2)%mod; S=add(S,tmp[x].v1.g(i)); //for(int y:E[1])if(y!=x)prod=prod*1ll*(i?f[y][i-1]+1:1)%mod; res=add(res,prod); //cout<<"test "<<x<<" "<<i<<" "<<prod<<endl; } } dfs2(1,0); res=add(ans[1],mod-res); printf("%d\n",res); } int main(){ //freopen("planb.in","r",stdin),freopen("planb.out","w",stdout); int t=read();up(i,1,t){ printf("Case #%d: ",i);slv(); } return 0; }