#include using namespace std; using ll=long long; using ull=unsigned long long; #define all(x) (x).begin(),(x).end() #ifdef DEBUG template ostream& operator << (ostream &out,vectora){ out<<'['; for(auto x:a)out< auto ary(T *a,int l,int r){ return vector{a+l,a+1+r}; } template void debug(T x){ cerr< void debug(T x,S...y){ cerr<>to[N]; void init(int lim){ static int n; if(lim<=n)return; for(int i=n+1;i<=lim;i++)fac[i]=1ll*fac[i-1]*i%mod; n=lim; } #define add(x,y) ((x)=((x)+(y))%mod) void dfs(int u,int fa,int flag){ int cnt=to[u].size()-1; if(!cnt){ f[u][flag?2:1]=1; return; } for(auto x:to[u])if(x.first^fa)dfs(x.first,u,a[x.second]); static int now=1,las=0,s[2][4]; memset(s[now],0,sizeof s[now]); s[now][3]=1; int res=0; for(auto x:to[u])if(x.first^fa){ int v,w; tie(v,w)=x; swap(now,las); memset(s[now],0,sizeof s[now]); for(int c:{0,1,2,3}){ add(s[now][c],1ll*s[las][c]*(f[v][1]+f[v][2])); } for(int c:{0,1,2}){ add(s[now][c],1ll*s[las][3]*f[v][c]); } res=( 1ll*res*(f[v][1]+f[v][2])+ 1ll*s[las][0]*(f[v][1]+f[v][2])+ 1ll*s[las][1]*(f[v][0]+f[v][2])+ 1ll*s[las][2]*(0u+f[v][0]+f[v][1]+f[v][2]) )%mod; } //if(u==2)debug(s[now][1]); add(f[u][0],1ll*s[now][0]*fac[cnt-1]); add(f[u][flag?2:1],1ll*s[now][1]*fac[cnt-1]); add(f[u][2],1ll*s[now][2]*fac[cnt-1]); add(f[u][0],1ll*res*fac[cnt-1]); //debug(u,ary(f[u],0,2)); } void work(){ read(n),read(m); init(n); for(int i=1,u,v;i1;u++); //debug(u); tie(v,w)=to[u][0]; dfs(v,u,a[w]); printf("%d\n",(f[v][0]+f[v][2])%mod); } void clear(){ fill(a+1,a+n,0); for(int i=1;i<=n;i++){ to[i].clear(); memset(f[i],0,sizeof f[i]); } } int main(){ freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); for(fac[0]=1,read(sid),read(T);T--;clear())work(); return 0; }