#include #define Mod 1000000007 using namespace std; int Qread() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar(); return x; } inline void add(int &a,int b){a+=b;if(a>=Mod) a-=Mod;} struct Edge{int v,id;}; vector ed[100010]; void add_edge(int u,int v,int id) { ed[u].push_back(Edge{v,id}); ed[v].push_back(Edge{u,id}); } int fac[100010],inv[100010]; int n,k; int u[100010],v[100010]; bool typ[100010]; int ans,gl; int f[100010][2]; void dfs(int a,int faid) { int lm=ed[a].size()-!!(faid),dc=ed[a].size()-1; if(lm) { int f0=0,f1=0,ret=0; for(Edge v:ed[a]) if(v.id!=faid) { dfs(v.v,v.id); ret=(ret +1ll*f0*f[v.id][1] +1ll*f1*f[v.id][0] +1ll*f1*f[v.id][1])%Mod; add(f0,f[v.id][0]), add(f1,f[v.id][1]); } ret=1ll*ret*inv[dc]%Mod*gl%Mod; add(ans,ret); if(faid) { f[faid][0]=1ll*f0*inv[dc]%Mod; f[faid][1]=1ll*f1*inv[dc]%Mod; } else f[faid][0]=f0,f[faid][1]=f1; } else f[faid][0]=1,f[faid][1]=0; if(typ[faid]) { add(f[faid][1],f[faid][0]); f[faid][0]=0; } if(faid==0&&lm==1) add(ans,1ll*f[faid][1]*gl%Mod); } void solve() { for(int i=1;i<=n;i++) vector().swap(ed[i]); memset(typ,0,(n+1)); memset(f,0,(n+5)<<3); ans=0,gl=1; n=Qread(),k=Qread(); for(int i=1;i