bool M1; #include #include #include using namespace std; using namespace __gnu_pbds; #define uint unsigned int #define ll long long #define ull unsigned int long long #define db double #define Pii pair #define Pll pair #define fir first #define sec second #define pc(x) __builtin_popcount(x) #define vec vector #define pb push_back #define qlr cerr<<"qlr\n" #define dyh cerr<<"dyh\n" #define uni(x,y) uniform_int_distribution(x,y)(rng) #define unl(x,y) uniform_int_distribution(x,y)(rng) #define unr(x,y) uniform_real_distribution(x,y)(rng) #define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--) #define look_memory cerr<<'\n'< inline void inc(T &a,T b){ if(b<0) b+=Mod; a+=b; if(a>=Mod) a-=Mod; } template inline void dec(T &a,T b){ if(b<0) b+=Mod; a-=b; if(a<0) a+=Mod; } template inline void muc(T &a,T b){ a=a*b%Mod; } template inline bool chkmin(T &a,T b){ if(a<=b) return 0; a=b; return 1; } template inline bool chkmax(T &a,T b){ if(a>=b) return 0; a=b; return 1; } struct IO{ #define N 1<<22 char buf[N],*p1=buf,*p2=buf; #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++) template void read(T &x){ x=0;char ch;int f=0; while((ch=gc())<'0'||ch>'9') f|=ch=='-'; while(x=(x<<1)+(x<<3)+(ch^48),(ch=gc())>='0'&&ch<='9'); if(f) x=~x+1; } #undef N }io; ll Num,T,n,K,ans; int a[100010]; ll fac[100010]; ll f[100010][2][2]; Pii E[100010]; vector e[100010]; ll Pow(ll a,ll b){ a%=Mod; ll res=1,base=a; while(b){ if(b&1) res=res*base%Mod; base=base*base%Mod; b>>=1; } return res; } void init(){ #define N 100000 fac[0]=1; F(i,1,N) fac[i]=fac[i-1]*i%Mod; #undef N } ll ask1(int x){ return fac[x-1]; } ll ask2(int x){ if(x==1) return 1; return fac[x-2]; } void dfs(int u,int fa){ for(auto i:e[u]){ int v=i.fir; if(v==fa) continue; dfs(v,u); } ll tf[2][2]; for(auto i:e[u]){ int v=i.fir; if(v==fa) continue; if(!i.sec) continue; memcpy(tf,f[v],sizeof(tf)); dec(tf[1][0],f[v][0][1]); dec(tf[1][1],f[v][0][1]); dec(tf[1][0],f[v][1][1]); dec(tf[1][1],f[v][1][1]); memcpy(f[v],tf,sizeof(f[v])); } ll g[3],tg[3]; g[0]=1,g[1]=0,g[2]=0; for(auto i:e[u]){ int v=i.fir; if(v==fa) continue; memset(tg,0,sizeof(tg)); F(i,0,2) tg[i]=(tg[i]+g[i]*f[v][0][1])%Mod; F(i,0,1) tg[i+1]=(tg[i+1]+g[i]*f[v][1][1])%Mod; memcpy(g,tg,sizeof(g)); } f[u][1][0]=g[2]*ask2(e[u].size())%Mod; f[u][1][1]=g[1]*ask2(e[u].size())%Mod; g[0]=1,g[1]=0; for(auto i:e[u]){ int v=i.fir; if(v==fa) continue; g[1]=(g[0]*f[v][1][0]+g[1]*f[v][0][1])%Mod; g[0]=g[0]*f[v][0][1]%Mod; } f[u][0][1]=g[0]*ask1(e[u].size())%Mod; f[u][1][0]=(f[u][1][0]+g[1]*ask1(e[u].size()))%Mod; } void solve(){ io.read(n),io.read(K); F(i,1,n) e[i].clear(); F(i,1,n-1) io.read(E[i].fir),io.read(E[i].sec); F(i,1,n-1) a[i]=0; F(i,1,K){ int x; io.read(x); a[x]=1; } F(i,1,n-1) e[E[i].fir].pb({E[i].sec,a[i]}),e[E[i].sec].pb({E[i].fir,a[i]}); dfs(1,0); ans=-f[1][1][0]; ans=(ans%Mod+Mod)%Mod; cout<