#include #define ll long long using namespace std; inline char gc(){ static char buf[1<<21],*p1=buf,*p2=buf; if(p2==p1) p2=(p1=buf)+fread(buf,1,1<<20,stdin); return *p1++; } inline int read(){ int x=0; char c=gc(); for(;c<'0'||c>'9';c=gc()); for(;c>='0'&&c<='9';c=gc())x=(x*10)+(c^48); return x; } const int N=1e5+10; const int mod=1e9+7; inline int qpow(int x,int y=mod-2){ int r=1; for(;y;x=(ll)x*x%mod,y>>=1) if(y&1) r=(ll)r*x%mod; return r; } int fac[N]; void init_fac(){ fac[0]=1; for(int i=1;i> g[N]; int f[N][7]; bool oks[N]; void dfs(int u,int fa){ for(int i=0;i<=6;i++) f[u][i]=0; f[u][0]=1; f[u][3]=1; f[u][5]=1; for(auto e:g[u]){ int v=e[0],w=e[1]; if(v==fa) continue; dfs(v,u); int tmp[7]; memset(tmp,0,sizeof(tmp)); int *F=f[u],*G=f[v]; auto t0=[&](){ tmp[0]=(tmp[0]+(ll)F[0]*G[0])%mod; tmp[1]=(tmp[1]+(ll)F[1]*G[3]+(ll)F[5]*G[1])%mod; tmp[2]=(tmp[2]+(ll)F[2]*G[3]+(ll)F[6]*G[4])%mod; tmp[3]=(tmp[3]+(ll)F[3]*G[3])%mod; tmp[4]=(tmp[4]+(ll)F[3]*G[4]+(ll)F[4]*G[3])%mod; tmp[5]=(tmp[5]+(ll)F[5]*G[3])%mod; tmp[6]=(tmp[6]+(ll)F[6]*G[3]+(ll)F[5]*G[4])%mod; }; auto t1=[&](){ tmp[1]=(tmp[1]+mod-(ll)F[5]*(G[3]+G[4])%mod)%mod; tmp[2]=(tmp[2]+mod-(ll)F[6]*(G[3]+G[4])%mod)%mod; tmp[4]=(tmp[4]+mod-(ll)F[3]*(G[3]+G[4])%mod)%mod; tmp[6]=(tmp[6]+mod-(ll)F[5]*(G[3]+G[4])%mod)%mod; }; t0(); if(oks[w]) t1(); for(int i=0;i<=6;i++) F[i]=tmp[i]; } // int tmp[5]; memset(tmp,0,sizeof(tmp)); f[u][0]=(ll)f[u][0]*fac[g[u].size()-1]%mod; f[u][1]=(ll)f[u][1]*fac[g[u].size()-1]%mod; if(g[u].size()>1) f[u][1]=(f[u][1]+(ll)f[u][2]*fac[g[u].size()-2]%mod)%mod; f[u][3]=(ll)f[u][3]*fac[g[u].size()-1]%mod; if(g[u].size()>1) f[u][4]=(ll)f[u][4]*fac[g[u].size()-2]%mod; else f[u][4]=0; // printf("%d: ",u); // for(int i=0;i<=6;i++) printf("%d ",f[u][i]); // puts(""); // printf("%d: %d %d %d %d\n",u,f[u][0],f[u][1],f[u][3],f[u][4]); } void solve(){ n=read(); k=read(); // cerr<