#include using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch&15); return f*x; } const int mod=1000000007; int c,t,n,k,u,re,v,e[100005],fac[100005],vl[100005],inv[100005],deg[100005]; vector > g[100005]; bitset<100005> vis; int Pow(int x,int y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res; } void dfs(int x,int fa,int val){ if(val&°[x]>=2) val=1ll*val*inv[deg[x]-1]%mod*fac[deg[x]-2]%mod; for(pair y:g[x]) if(y.first^fa) if(vis[y.second]){ re=(re-val)%mod,dfs(y.first,x,1); if(vl[x]) re=(re-1ll*inv[deg[x]-1]*fac[deg[x]-2]%mod*vl[x]%mod)%mod; vl[x]++; } else{ dfs(y.first,x,val); if(vl[y.first]){ if(vl[x]) re=(re-1ll*inv[deg[x]-1]*fac[deg[x]-2]%mod*vl[x]%mod*vl[y.first]%mod* inv[deg[y.first]-1]%mod*fac[deg[y.first]-2]%mod)%mod; vl[x]=(vl[x]+1ll*vl[y.first]*inv[deg[y.first]-1]%mod*fac[deg[y.first]-2]%mod)%mod; } } // if(deg[x]>=2) vl[x]=1ll*vl[x]*inv[deg[x]-1]%mod*fac[deg[x]-2]%mod; } int main(){ freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); c=read(),t=read(),fac[0]=inv[0]=1; for(int i=1;i<=100000;i++) fac[i]=1ll*fac[i-1]*i%mod; inv[100000]=Pow(fac[100000],mod-2); for(int i=99999;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; while(t--){ n=read(),k=read(),memset(deg,0,sizeof(deg)),memset(vl,0,sizeof(vl)),re=k,vis.reset(); for(int i=1;i<=n;i++) g[i].clear(); for(int i=1;i