#include #include #define F(i,l,r) for(int i=(l),i##_end=(r);i=MOD)x-=MOD;} int qpow(ull a,int b,ull c=1) { for(;b;b>>=1,(a*=a)%=MOD)if(b&1)(c*=a)%=MOD; return (int)c; } struct adj_list { int *l,*r; void emplace_back(int x){*r++=x;} int *begin(){return l;} int *end(){return r;} }adj[N]; int fac[N],invfac[N],inv[N]; int n,k,ee[N][2],aa[2*N],deg[N],dep[N],ans,f[N][2]; bool is[N]; void dfs1(int u,int fa) { for(int v:adj[u])if(v!=fa)dep[v]=dep[u]+1,dfs1(v,u); } void dfs2(int u,int fa) { for(int v:adj[u])if(v!=fa)dfs2(v,u); f[u][0]=0;f[u][1]=0; bool leaf=true; int c=0; for(int v:adj[u])if(v!=fa) { leaf=false; if(is[v])reduce(f[v][1]+=f[v][0]),f[v][0]=0; c=(int)((c+(ull)f[u][0]*f[v][1]+(ull)f[u][1]*f[v][0]+(ull)f[u][1]*f[v][1])%MOD); reduce(f[u][0]+=f[v][0]); reduce(f[u][1]+=f[v][1]); } if(leaf)f[u][0]=1; else { ans=(int)((ans+(ull)inv[deg[u]-1]*c)%MOD); f[u][0]=(int)((ull)inv[deg[u]-1]*f[u][0]%MOD); f[u][1]=(int)((ull)inv[deg[u]-1]*f[u][1]%MOD); } } int solve() { scanf("%d%d",&n,&k); F(i,0,n)deg[i]=0; F(i,0,n-1) { int &u=ee[i][0],&v=ee[i][1]; scanf("%d%d",&u,&v);--u,--v; ++deg[u];++deg[v]; } adj[0]={aa,aa}; F(i,0,n)adj[i+1].l=adj[i].l+deg[i],adj[i+1].r=adj[i].r+deg[i]; F(i,0,n-1) { const int &u=ee[i][0],&v=ee[i][1]; adj[u].emplace_back(v); adj[v].emplace_back(u); } if(n==2) { F(i,0,k)scanf("%*d"); return 1; } int rt=0; while(deg[rt]==1)++rt; dep[rt]=0; dfs1(rt,rt); F(i,0,n)is[i]=false; F(i,0,k) { int e;scanf("%d",&e);--e; int &u=ee[e][0],&v=ee[e][1]; if(dep[u]>dep[v])swap(u,v); is[v]=true; } ans=0; dfs2(rt,rt); F(i,0,n)ans=(int)((ull)ans*fac[deg[i]-1]%MOD); return ans; } int main() { #ifndef LOCAL #ifndef ONLINE_JUDGE freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); #endif #endif F(i,fac[0]=1,N)fac[i]=(int)((ull)fac[i-1]*i%MOD); invfac[N-1]=qpow(fac[N-1],MOD-2); for(int i=N;--i;)invfac[i-1]=(int)((ull)invfac[i]*i%MOD); F(i,1,N)inv[i]=(int)((ull)invfac[i]*fac[i-1]%MOD); int tt;scanf("%*d%d",&tt); while(tt--)printf("%d\n",solve()); return 0; }