#include #define int long long #define fi first #define se second #define eb emplace_back #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef pair pii; typedef vector vi; typedef vector vp; int read() { int x=0,w=1; char c=getchar(); while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();} while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} return x*w; } const int N=1e5+5,mod=1e9+7; int ccc,T,n,k,deg[N],fac[N],rt[N],prod,eu[N],ev[N],f[N][2][3]; vp e[N]; void dfs(int u,int fid) { for(auto [v,id]:e[u]) if(id!=fid) dfs(v,id); rep(x,0,1) rep(y,0,2) f[u][x][y]=0; static int g[3]; g[0]=g[1]=g[2]=0; g[0]=1; for(auto [v,id]:e[u]) if(id!=fid) { g[1]=(g[1]*f[v][1][0]+g[0]*(f[v][0][1]+f[v][0][2]))%mod; g[0]=g[0]*f[v][1][0]%mod; } f[u][0][1]=g[1]; g[0]=g[1]=g[2]=0; g[0]=1; for(auto [v,id]:e[u]) if(id!=fid) { g[2]=(g[2]*f[v][1][0]+g[1]*(f[v][1][1]))%mod; g[1]=(g[1]*f[v][1][0]+g[0]*(f[v][1][1]))%mod; g[0]=g[0]*f[v][1][0]%mod; } f[u][1][0]=g[0], f[u][1][1]=g[1], f[u][0][2]=g[2]; rep(x,0,1) rep(y,0,2) if(deg[u]-x-y>=0) f[u][x][y]=f[u][x][y]*fac[deg[u]-x-y]%mod; if(rt[fid]) { int gg=f[u][1][0]+f[u][1][1]; gg=(2*mod-gg)%mod; f[u][1][1]=(f[u][1][1]+gg)%mod; f[u][0][1]=(f[u][0][1]+gg)%mod; } //rep(x,0,1) rep(y,0,2){ //if(f[u][x][y]) cout<100?f[u][x][y]-mod:f[u][x][y])<