#include #include #include #include #include #include using namespace std; #define int long long #define P 1000000007ll int qp(int a,int b){ int ans=1; while(b){ if(b%2)ans=ans*a%P; a=a*a%P; b/=2; } return ans; } int M(int i){ return (i%P+P)%P; } int inv(int i){ if(i==0)return 0; if(i==1)return 1; int q=P/i,r=P%i; if(r<=i/2)return M(-q*inv(r)); return M((q+1)*inv(i-r)); } int fac[100010]; int A[100010],B[100010],sp[100010]; int to[200010],nxt[200010],head[100010],cnt; int deg[100010],fa[100010]; int ha[100010],hb[100010]; int ans; void dfs(int u,int f){ fa[u]=f; for(int i=head[u];i;i=nxt[i])if(to[i]!=f)dfs(to[i],u); } void add(int a,int b){ to[++cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; } void dfs2(int i){ A[i]=fac[deg[i]-1]; int I=inv(deg[i]-1),C=0; for(int J=head[i];J;J=nxt[J]){ int j=to[J]; if(j==fa[i])continue; dfs2(j); A[i]=A[i]*A[j]%P; if(sp[j])B[i]=(B[i]+I)%P,C=(C+I*I)%P; else B[i]=(B[i]+B[j]*I)%P,C=(C+B[j]*I%P*B[j]%P*I)%P; } if(sp[i])ans=(ans+B[i])%P; ans=(ans+M((B[i]*B[i]%P-C)*inv(2)%P*(deg[i]-1)))%P; } signed main(){ freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); int c,T; scanf("%lld %lld",&c,&T); fac[0]=1; for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%P; for(int I=1;I<=T;I++){ int n,k; scanf("%lld %lld",&n,&k); cnt=0; for(int i=1;i<=n;i++)head[i]=deg[i]=sp[i]=A[i]=B[i]=0; for(int i=1;i