#include using namespace std; namespace io { constexpr int S1=1<<20; char buf1[S1],*l1,*r1; inline char getc() { return ((l1==r1&&(r1=(l1=buf1)+fread(buf1,1,S1,stdin)),l1!=r1)?*l1++:EOF); } templateinline T read() { T x=0,y=1; char c=getc(); for(;c<'0'||c>'9';c=getc()) if(c=='-') y=-1; for(;c>='0'&&c<='9';c=getc()) x=c-'0'+x*10; return x*y; } constexpr int S2=1<<20; char buf2[S2],*l2=buf2; inline void putc(char c) { l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=c; } int st[42]; templateinline void write(T x,char end='\n') { if(x<0) putc('-'),x=-x; int tp=0; do st[++tp]=x%10; while(x/=10); while(tp) putc(st[tp--]+'0'); if(end) putc(end); } inline void ps(const char*a,char end='\n') { for(const char*p=a;*p;p++) putc(*p); if(end) putc(end); } struct end { ~end() { fwrite(buf2,1,l2-buf2,stdout); } }ender; } using io::getc; using io::read; using io::putc; using io::write; using io::ps; constexpr long long mod=1000000007; constexpr int MN=100005; int n,K,u[MN],v[MN],fa[MN]; long long fac[MN],f[MN][4]; vectorG[MN]; bool fl[MN]; void dfs1(int x,int F) { fa[x]=F; for(int y:G[x]) if(y!=F) dfs1(y,x); } void dfs2(int x) { if(G[x].size()==1) { f[x][1]=f[x][2]=f[x][3]=0; f[x][0]=f[x][1+fl[x]]=1; return; } for(int y:G[x]) if(y!=fa[x]) dfs2(y); long long t[3][2]={fac[G[x].size()-2]},g[3][2]; for(int y:G[x]) { if(y==fa[x]) continue; memset(g,0,sizeof g); for(int i=0;i<3;i++) for(int j=0;j<2;j++) { g[i][j]=(g[i][j]+t[i][j]*f[y][0])%mod; if(i<2) { g[i+1][j]=(g[i+1][j]+t[i][j]*f[y][1])%mod; g[i+1][1]=(g[i+1][1]+t[i][j]*f[y][2])%mod; } } memcpy(t,g,sizeof t); } f[x][0]=(t[1][0]+t[1][1])%mod; f[x][1]=(!fl[x])*t[1][0]; f[x][2]=(t[1][1]+fl[x]*t[1][0])%mod; f[x][3]=t[2][1]; memset(t,0,sizeof t); t[0][0]=fac[G[x].size()-2]; for(int y:G[x]) { if(y==fa[x]) continue; memset(g,0,sizeof g); for(int i=0;i<3;i++) for(int j=0;j<2;j++) { g[i][j]=(g[i][j]+t[i][j]*f[y][0])%mod; if(i<2) { g[i+1][j]=(g[i+1][j]+t[i][j]*(f[y][1]+f[y][2]))%mod; if(!j) g[i+1][1]=(g[i+1][1]+t[i][j]*f[y][3])%mod; } } memcpy(t,g,sizeof t); } f[x][3]=(f[x][3]+t[1][1]+t[2][1])%mod; } inline void work() { n=read(),K=read(); *fac=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; for(int i=1;i