#include #define ll long long using namespace std; const int N=2e5+100; const ll mod=1e9+7; int tid,T; int n,k; ll fac[N],inv[N]; ll ans; ll ksm(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void dd(int &v) { v=0; char ch=getchar(); while(ch<'0'||ch>'9') { ch=getchar(); } while(ch>='0'&&ch<='9') { v=v*10+ch-48; ch=getchar(); } } void init() { fac[0]=inv[0]=1;//!!! for(int i=1;i son[N]; int dep[N]; bool tag[N]; ll dp[N]; void dfs1(int x,int ft) { dep[x]=dep[ft]+1; for(int u:son[x]) { if(u==ft) continue ; dfs1(u,x); } } void dfs2(int x,int ft) { for(int u:son[x]) { if(u==ft) continue ; dfs2(u,x); ans=(ans+dp[x]*dp[u]%mod*inv[g[x]-1]%mod)%mod; if(tag[u]) { ans=(ans+dp[x]*((mod-1)*dp[u]%mod+(mod-1))%mod*inv[g[x]-1]%mod)%mod; ans=(ans+(mod-1)*dp[u]+(mod-1))%mod; } dp[x]=(dp[x]+dp[u])%mod; if(tag[u]) { dp[x]=(dp[x]+(mod-1)*dp[u]+(mod-1))%mod; } } dp[x]=dp[x]*inv[g[x]-1]%mod; } void work() { dd(n); dd(k); for(int i=1;i<=n;++i) { son[i].clear(); } memset(tag,0,sizeof(tag)); memset(g,0,sizeof(g)); memset(dp,0,sizeof(dp)); for(int i=1,x,y;i