#include #include #include #define int long long using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=100010,mod=1e9+7,iv2=5e8+4; int t,n,k,u[N],v[N],w[N],in[N]; int fr[N],nex[N<<1],to[N<<1],fl[N<<1],ct; int rt,jc[N],g[N],ig[N],f[N],gf[N],ff[N],ans; int ksm(int p,int k){ int x=1; while(k){ if(k&1)x=x*p%mod; p=p*p%mod; k>>=1; } return x; } void add(int x,int y,int z){ nex[++ct]=fr[x]; to[ct]=y; fl[ct]=z; fr[x]=ct; } void dfs(int x,int fa){ g[x]=ig[x]=1;f[x]=gf[x]=ff[x]=0;int tt=0; for(int i=fr[x];i;i=nex[i]){ int y=to[i]; if(y==fa)continue; dfs(y,x); int a=g[y],b=f[y]; if(fl[i])b=a; ff[x]=(ff[x]*a+f[x]*a+gf[x]*b)%mod; gf[x]=(gf[x]*a+g[x]*(a-b+mod))%mod; f[x]=(f[x]*a+g[x]*b)%mod; g[x]=g[x]*a%mod; tt++; } g[x]=g[x]*jc[tt]%mod; f[x]=f[x]*jc[tt-1]%mod; if(tt>=2)ff[x]=ff[x]*jc[tt-2]%mod; ig[x]=ksm(g[x],mod-2); if(x==rt)g[x]=g[x]*ksm(tt,mod-2)%mod; // cout<=2&&!rt)rt=i; } dfs(rt,0); dfs2(rt,0,1); cout<