#include #define LL long long #define LLL __int128 #define uint unsigned #define ldb long double #define uLL unsigned long long using namespace std; char rdc[1<<18],*rS,*rT; #define gc() (rS==rT?rT=rdc+fread(rS=rdc,1,1<<18,stdin),rS==rT?EOF:*rS++:*rS++) templateinline void read(T&x){ x=0;char c;bool f=1; while(!isdigit(c=gc()))if(c=='-')f=0; if(f)do x=x*10+(c&15);while(isdigit(c=gc())); else do x=x*10-(c&15);while(isdigit(c=gc())); } const int N=1e5+5,Mod=1e9+7; int typ; int n,k,all,ans; vector>G[N]; int vs[N],frc[N],ivf[N],f[N],g[N]; inline int qpow(int x,int y,int z=1){ for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z; } inline void dfs(int u,int fa){ f[u]=0; for(auto [v,w]:G[u])if(v!=fa){ dfs(v,u); if(vs[w]){ if(f[v]){ f[v]=(1ll*f[v]*ivf[G[v].size()-1]%Mod*frc[G[v].size()-2])%Mod; ans=(ans-1ll*f[v]*all)%Mod; } f[v]=1; } else if(f[v])f[v]=(1ll*f[v]*ivf[G[v].size()-1]%Mod*frc[G[v].size()-2])%Mod; if(f[u]&&f[v])ans=(ans-1ll*f[u]*f[v]%Mod*all%Mod*ivf[G[u].size()-1]%Mod*frc[G[u].size()-2])%Mod; f[u]=(f[u]+f[v])%Mod; } } inline void MAIN(){ read(n),read(k); for(int i=1;i<=n;++i)G[i].clear(),vs[i]=0; frc[0]=1; for(int i=1;i<=n;++i)frc[i]=1ll*frc[i-1]*i%Mod; ivf[n]=qpow(frc[n],Mod-2); for(int i=n;i>=1;--i)ivf[i-1]=1ll*ivf[i]*i%Mod; for(int i=1;isync_with_stdio(0); freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); int t=1;read(typ),read(t);while(t--)MAIN(); return 0; }