#include using namespace std; typedef long long ll; typedef pair pii; #define TIME (1e3*clock()/CLOCKS_PER_SEC) #define debug(fmt,...) fprintf(stderr, fmt, __VA_ARGS__) #define debugln(fmt,...) \ fprintf(stderr,"[%d] " fmt, __LINE__,__VA_ARGS__) bool memBeg; constexpr int mod=1e9+7; void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;} void dec(int &x,int y) {x-=y; x+=(x<0)*mod;} int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;} int sub(int x,int y) {return (x>=1,x=1ll*x*x%mod) { if(times&1) ret=1ll*ret*x%mod; } return ret; } char fetch() { return getchar(); } int readint() { // only for non-negative integers char c=fetch(); int ret=0; for(;c<'0'||c>'9';c=fetch()); for(;'0'<=c&&c<='9';c=fetch()) { ret=ret*10+(c&15); } return ret; } constexpr int maxn=1e5+5,inv2=(mod+1)/2; int fac[maxn],ifac[maxn],head[maxn],to[maxn<<1],nxt[maxn<<1],tot; void add_edge(int u,int v) { to[tot]=v; nxt[tot]=head[u]; head[u]=tot++; to[tot]=u; nxt[tot]=head[v]; head[v]=tot++; } int wys[maxn<<1],iwys[maxn<<1],pwys[maxn<<1]; void dfs1(int u,int pre) { if(pre!=-1) wys[pre]=1; int cnt=0; for(int i=head[u];~i;i=nxt[i]) { if((i^1)==pre) continue; cnt++; dfs1(to[i],i); if(pre!=-1) wys[pre]=1ll*wys[pre]*wys[i]%mod; } if(pre!=-1) wys[pre]=1ll*wys[pre]*fac[cnt]%mod; } void dfs2(int u,int pre) { vector arr,pf,sf; for(int i=head[u];~i;i=nxt[i]) { if((i^1)==pre) continue; arr.emplace_back(wys[i]); } pf.resize(arr.size()); sf.resize(arr.size()); for(int i=0,f=1;i<(int)arr.size();i++) { f=1ll*f*arr[i]%mod; pf[i]=f; } for(int i=(int)arr.size()-1,f=1;i>=0;i--) { f=1ll*f*arr[i]%mod; sf[i]=f; } for(int i=head[u],p=0;~i;i=nxt[i]) { if((i^1)==pre) continue; int cur=(pre==-1)?1:wys[pre^1]; if(p) cur=1ll*cur*pf[p-1]%mod; if(p+1<(int)arr.size()) cur=1ll*cur*sf[p+1]%mod; int cnt=(int)arr.size()-1+(pre!=-1); wys[i^1]=1ll*cur*fac[cnt]%mod; p++; dfs2(to[i],i); } } bool key[maxn],done[maxn<<1]; int more,up[maxn]; void dfs3(int u,int pre) { up[u]=0; int full=1,cnt=0; for(int i=head[u];~i;i=nxt[i]) { if((i^1)!=pre) { full=1ll*full*wys[i]%mod; cnt++; } } if(cnt) full=1ll*full*fac[cnt-1]%mod; for(int i=head[u];~i;i=nxt[i]) { if((i^1)==pre) continue; dfs3(to[i],i); up[u]=(up[u]+1ll*up[to[i]]*iwys[i]%mod*full)%mod; } if(pre!=-1&&key[pre>>1]) { if(!done[pre]) { // debug("pre = %d, u = %d, up = %d, wys = %d\n",pre,u,up[u],wys[pre^1]); more=(more+1ll*up[u]*wys[pre^1])%mod; done[pre]=true; } up[u]=wys[pre]; } cnt=0; full=1; for(int i=head[u];~i;i=nxt[i]) { if((i^1)!=pre) { full=1ll*full*wys[i]%mod; cnt++; } } if(pre!=-1) { full=1ll*full*wys[pre^1]%mod; cnt++; } if(cnt<2) return; full=1ll*full*fac[cnt-2]%mod; int sum=0; for(int i=head[u];~i;i=nxt[i]) { if((i^1)!=pre) { sum=(sum+1ll*iwys[i]*up[to[i]])%mod; } } for(int i=head[u];~i;i=nxt[i]) { if((i^1)!=pre) { int cur=1ll*iwys[i]*up[to[i]]%mod; dec(sum,cur); more=(more+1ll*cur*sum%mod*full)%mod; } } } void mian() { memset(head,-1,sizeof(head)); tot=0; int n=readint(),K=readint(); for(int i=1;i=0;i--) { iwys[i]=1ll*iwys[i+1]*wys[i]%mod; } iwys[0]=iwys[1]; for(int i=1;i<2*(n-1);i++) { iwys[i]=1ll*iwys[i+1]*pwys[i]%mod; } dfs3(1,-1); // debug("more = %d\n",more); dec(ret,more); // for(int i=0;i<2*(n-1);i++) { // assert(1ll*iwys[i]*wys[i]%mod==1); // } printf("%d\n",ret); } bool memEn; void fl() { freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); } int main() { debug("%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0); fl(); fac[0]=1; for(int i=1;i=0;i--) { ifac[i]=1ll*ifac[i+1]*(i+1)%mod; } int tak_id=readint(),_=readint(); while(_--) mian(); return 0; } /* g++ traverse.cpp -o traverse -std=c++14 -Wall -Wextra -Wshadow -O2 # -fsanitize=address,undefined */