#include #define N 200005 #define mod 1000000007 #define gc getchar() using namespace std; int read(){ int x=0; char ch; while((ch=gc)<48); while(ch>=48) x=x*10+ch-48,ch=gc; return x; } int md(int x){ return x>=mod?x-mod:x; } int power(int x,int y){ int res=1; while(y){ if(y&1) res=1ll*res*x%mod; x=1ll*x*x%mod; y=y/2; } return res; } int fac[N],nv[N]; int n,k,rt[N]; int h[N],to[N],nxt[N],cnt; int key[N]; void jb(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } int sz[N],ans,sum,f[N]; void dfs(int u,int fa,int ty){ f[u]=0; int ad=0; for(int i=h[u];i!=0;i=nxt[i]){ int v=to[i]; if(v==fa) continue; dfs(v,u,key[i/2]); ad=(ad+1ll*f[u]*f[v])%mod; f[u]=md(f[u]+f[v]); } sum=(sum+1ll*ad*nv[rt[u]-1])%mod; f[u]=1ll*f[u]*nv[rt[u]-1]%mod; if(ty==1){ sum=md(sum+f[u]); f[u]=1; } } void solve(){ n=read();k=read(); cnt=1; for(int i=1;i<=n;i++) h[i]=rt[i]=0; for(int i=1;i