#include using namespace std; constexpr int N=1e5+9,S=1<<22,mod=1e9+7,i2=(mod+1)>>1; char buf[S],*p1,*p2; inline int nc(){ if(p1==p2){ p2=(p1=buf)+cin.read(buf,S).gcount(); if(p1==p2)return EOF; }return *p1++; } inline int rd(){ char ch; while(!isdigit(ch=nc())); int x=ch&0xf; while(isdigit(ch=nc()))x=x*10+(ch&0xf); return x; } inline void mul(int&x,int y){ x=1ll*x*y%mod; } int n,k,eu[N],ev[N],fa[N],f[N],g[N],h[N],fac[N]; bool isk[N],isn[N]; vectores[N]; void dfs(int x){ for(int y:es[x]){ es[y].erase(find(es[y].begin(),es[y].end(),x)); fa[y]=x,dfs(y); } } void calc(int x){ if(int c=es[x].size()){ f[x]=fac[c]; for(int y:es[x])calc(y),mul(f[x],f[y]); int mf=1,mg=0,mh=0,mt=0; for(int i=0;i1){ g[x]=(1ll*g[x]*c+1ll*mh*(c-1))%mod; if(isk[x])h[x]=f[x]; else if((h[x]+=mt)>=mod)h[x]-=mod; } }else f[x]=1,g[x]=0,h[x]=isk[x]; } signed main(){ freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); cin.tie(nullptr)->sync_with_stdio(false); fac[0]=1; for(int i=1;i=mod)g[1]-=mod; cout<