#include #include #define ll long long #define clr(p) memset(p,0,sizeof(p)) using namespace std; int read(){ int re=0,c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') re=(re<<3)+(re<<1)+(c^48),c=getchar(); return re; } const int maxn=1e5+5; const ll mod=1e9+7; struct L{ int v,bro,id; }li[maxn*2]; int cid,n,k,du[maxn],head[maxn],cnt,isk[maxn],pld[maxn]; ll po[maxn],inv[maxn],dp[maxn][2],ans; void init(){ clr(du);clr(head);clr(dp);clr(isk); cnt=ans=0; } void add(int u,int v,int id){ li[++cnt]=(L){v,head[u],id},head[u]=cnt; } void dfs(int u,int pr) { if(du[u]==1&&u!=1) { dp[u][isk[pld[u]]]=1; return; } for (int i=head[u];i;i=li[i].bro){ int v=li[i].v; if(v==pr) continue; pld[v]=li[i].id,dfs(v,u); ll adv=(dp[u][1]*dp[v][1]+dp[u][0]*dp[v][1]+dp[u][1]*dp[v][0])%mod*inv[du[u]-1]%mod; ans=(ans+adv)%mod; dp[u][0]=(dp[u][0]+dp[v][0])%mod,dp[u][1]=(dp[u][1]+dp[v][1])%mod; } if(isk[pld[u]]) dp[u][1]=(dp[u][1]+dp[u][0])%mod,dp[u][0]=0; dp[u][1]=dp[u][1]*inv[du[u]-1]%mod,dp[u][0]=dp[u][0]*inv[du[u]-1]%mod; if(du[u]==1&&u==1) { ans=(ans+dp[u][1])%mod; } } void solve() { n=read(),k=read(); init(); po[0]=inv[0]=inv[1]=1; for (int i=1;i<=n;i++) po[i]=po[i-1]*i%mod; for (int i=2;i<=n;i++) inv[i]=mod-inv[mod%i]*(mod/i)%mod; for (int i=1;i