stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define Int register int

#define mod 1000000007

#define MAXN 5005



template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}



int mul (int a,int b){return 1ll * a * b % mod;}

int dec (int a,int b){return a >= b ? a - b : a + mod - b;}

int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}



int n,top = 1,to[MAXN << 1],nxt[MAXN << 1],head[MAXN],t[MAXN],g[MAXN],dp[MAXN][MAXN],siz[MAXN];

void Add_Edge (int u,int v){

	to[++ top] = v,nxt[top] = head[u],head[u] = top;

	to[++ top] = u,nxt[top] = head[v],head[v] = top;

}

void dfs (int u,int fa){

	siz[u] = dp[u][1] = 1;

	for (Int i = head[u];i;i = nxt[i]){

		int v = to[i];

		if (v == fa) continue;

		dfs (v,u);

		for (Int j = 0;j <= siz[u];++ j) t[j] = dp[u][j],dp[u][j] = 0;

		for (Int j = 0;j <= siz[u];++ j)

			for (Int k = 0;k <= siz[v];++ k)

				dp[u][j + k] = add (dp[u][j + k],mul (dp[v][k],t[j]));

		siz[u] += siz[v]; 

	}

	for (Int i = 1;i <= siz[u];++ i) dp[u][0] = dec (dp[u][0],mul (dp[u][i],i & 1 ? 0 : g[i]));

}



signed main(){

	read (n);

	for (Int i = 2,u,v;i <= n;++ i) read (u,v),Add_Edge (u,v);

	g[0] = 1;for (Int i = 2;i <= n;++ i) g[i] = mul (g[i - 2],i - 1);

	dfs (1,0),write (dec (0,dp[1][0])),putchar ('\n');

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



namespace TYC

{

	typedef long long ll;

	const int N = 5005, mod = 1e9 + 7;



	int n, F[N][N], V[N], Siz[N];

	vector<int> E[N];



	inline int read()

	{

		int x = 0, f = 0, ch = getchar();

		while (!isdigit(ch))

			f |= (ch == '-'), ch = getchar();

		while (isdigit(ch))

			x = x * 10 + ch - '0', ch = getchar();

		return f ? -x : x;

	}



	void dfs(const int u, const int f)

	{

		Siz[u] = 1;

		F[u][1] = 1;

		for (int v : E[u])

			if (v != f)

			{

				dfs(v, u);

				static int tmp[N];

				memcpy(tmp, F[u], sizeof(int[Siz[u] + 1]));

				memset(F[u], 0, sizeof(int[Siz[u] + 1]));

				for (int a = 1; a <= Siz[u]; a++)

					for (int b = 0; b <= Siz[v]; b++)

						(F[u][a + b] += int((ll)tmp[a] * F[v][b] % mod)) %= mod;

				Siz[u] += Siz[v];

			}

		for (int i = 2; i <= Siz[u]; i += 2)

			(F[u][0] += mod - int((ll)F[u][i] * V[i] % mod)) %= mod;

	}



	void work()

	{

		n = read();

		for (int i = 1; i < n; i++)

		{

			int u = read(), v = read();

			E[u].push_back(v);

			E[v].push_back(u);

		}

		V[2] = 1;

		for (int i = 4; i <= n; i += 2)

			V[i] = int((ll)V[i - 2] * (i - 1) % mod);

		dfs(1, 0);

		printf("%d\n", mod - F[1][0]);

	}

}



int main()

{

	TYC::work();

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int mod = 1e9 + 7;

const int MAXN = 5005;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



struct edge

{

	int to, nxt;

}Graph[MAXN << 1];



int tmp[MAXN];

int f[MAXN][MAXN], g[MAXN];

int head[MAXN], siz[MAXN];

int N, cnt;



void sub( int &x, const int v ) { x = ( x < v ? x + mod - v : x - v ); }

void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }



void addEdge( const int from, const int to )

{

	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];

	head[from] = cnt;

}



void DFS( const int u, const int fa )

{

	f[u][1] = 1, siz[u] = 1;

	for( int i = head[u], v ; i ; i = Graph[i].nxt )

		if( ( v = Graph[i].to ) ^ fa )

		{

			DFS( v, u );

			for( int i = 0 ; i <= siz[u] + siz[v] ; i ++ ) tmp[i] = 0; 

			for( int j = siz[u] ; j ; j -- )

				for( int k = siz[v] ; ~ k ; k -- )

					add( tmp[j + k], 1ll * f[u][j] * f[v][k] % mod );

			siz[u] += siz[v];

			for( int i = 0 ; i <= siz[u] ; i ++ ) f[u][i] = tmp[i];

		}

	for( int i = 1 ; i <= siz[u] ; i ++ )

		sub( f[u][0], 1ll * f[u][i] * g[i] % mod );

}



int main()

{

	read( N );

	for( int i = 1, a, b ; i < N ; i ++ )

		read( a ), read( b ), addEdge( a, b ), addEdge( b, a );

	g[2] = 1;

	for( int i = 4 ; i <= N ; i += 2 )

		g[i] = 1ll * g[i - 2] * ( i - 1 ) % mod;

	DFS( 1, 0 );

	write( ( mod - f[1][0] ) % mod ), putchar( '\n' );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define re register int

#define F(x,y,z) for(re x=y;x<=z;x++)

#define FOR(x,y,z) for(re x=y;x>=z;x--)

typedef long long ll;

#define I inline void

#define IN inline int

#define C(x,y) memset(x,y,sizeof(x))

#define STS system("pause")

template<class D>I read(D &res){

	res=0;register D g=1;register char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')g=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		res=(res<<3)+(res<<1)+(ch^48);

		ch=getchar();

	}

	res*=g;

}

const int Mod=1e9+7;

vector<int>e[5050];

int n,m,ans,X,Y,f[5050][5050],s[5050],siz[5050];

I add(int &x,int y){(x+=y)>=Mod?x-=Mod:0;}

I D_1(int x,int fa){

	f[x][1]=1;siz[x]=1;

	for(auto d:e[x]){

		if(d==fa)continue;

		D_1(d,x);static int g[5050];

		F(i,0,siz[x]+siz[d])g[i]=0;

		F(i,1,siz[x])F(j,1,siz[d]){

			add(g[i],Mod-(ll)f[x][i]*f[d][j]%Mod*s[j]%Mod);

			add(g[i+j],(ll)f[x][i]*f[d][j]%Mod);

		}

		siz[x]+=siz[d];F(i,0,siz[x])f[x][i]=g[i];

	}

}

int main(){

	read(n);

	F(i,1,n-1){

		read(X);read(Y);e[X].emplace_back(Y);e[Y].emplace_back(X);

	}

	s[0]=1;for(re i=2;i<=n;i+=2)s[i]=(ll)s[i-2]*(i-1)%Mod;

	D_1(1,0);

	for(re i=2;i<=n;i+=2)add(ans,(ll)f[1][i]*s[i]%Mod);

	printf("%d",ans);

	return 0;

}




// Optimized solution to the same problem (faster):
#include <cstdio>



const int mod = 1e9 + 7;

const int MAXN = 5005;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



struct edge

{

	int to, nxt;

}Graph[MAXN << 1];



int tmp[MAXN];

int f[MAXN][MAXN], g[MAXN];

int head[MAXN], siz[MAXN];

int N, cnt;



void sub( int &x, const int v ) { x = ( x < v ? x + mod - v : x - v ); }

void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }



void addEdge( const int from, const int to )

{

	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];

	head[from] = cnt;

}



void DFS( const int u, const int fa )

{

	f[u][1] = 1, siz[u] = 1;

	for( int i = head[u], v ; i ; i = Graph[i].nxt )

		if( ( v = Graph[i].to ) ^ fa )

		{

			DFS( v, u );

			for( int i = 0 ; i <= siz[u] + siz[v] ; i ++ ) tmp[i] = 0; 

			for( int j = siz[u] ; j ; j -- )

				for( int k = siz[v] ; ~ k ; k -- )

					add( tmp[j + k], 1ll * f[u][j] * f[v][k] % mod );

			siz[u] += siz[v];

			for( int i = 0 ; i <= siz[u] ; i ++ ) f[u][i] = tmp[i];

		}

	for( int i = 1 ; i <= siz[u] ; i ++ )

		sub( f[u][0], 1ll * f[u][i] * g[i] % mod );

}



int main()

{

	read( N );

	for( int i = 1, a, b ; i < N ; i ++ )

		read( a ), read( b ), addEdge( a, b ), addEdge( b, a );

	g[2] = 1;

	for( int i = 4 ; i <= N ; i += 2 )

		g[i] = 1ll * g[i - 2] * ( i - 1 ) % mod;

	DFS( 1, 0 );

	write( ( mod - f[1][0] ) % mod ), putchar( '\n' );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#define LL long long

using namespace std;

int n,tot;

const int N=5010,mod=1e9+7;

int head[N],to[N<<1],nt[N<<1],siz[N],f[N],dp[N][N],t[N];

void add(int f,int t)

{

	to[++tot]=t;nt[tot]=head[f];head[f]=tot;

}

void dfs(int x,int fa)

{

	siz[x]=1;dp[x][1]=1;

	for(int i=head[x];i;i=nt[i])

		if(to[i]!=fa)

		{

			dfs(to[i],x);

			for(int j=0;j<=siz[x];++j)t[j]=dp[x][j],dp[x][j]=0;

			for(int j=0;j<=siz[x];++j)

				for(int k=0;k<=siz[to[i]];++k)

					dp[x][j+k]=((LL)dp[x][j+k]+(LL)t[j]*dp[to[i]][k])%mod;				

			siz[x]+=siz[to[i]];

		}

	for(int i=0;i<=siz[x];++i)

		dp[x][0]=((LL)dp[x][0]-(LL)dp[x][i]*f[i])%mod;

}

int main()

{

	cin>>n;

	for(int i=1,x,y;i<n;++i)

		scanf("%d%d",&x,&y),add(x,y),add(y,x);

	f[0]=1;

	for(int i=2;i<=n;i+=2)f[i]=(LL)f[i-2]*(i-1)%mod;

	dfs(1,0);

	cout<<(mod-dp[1][0])%mod;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int mod = 1e9 + 7;

const int MAXN = 5005;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



struct edge

{

	int to, nxt;

}Graph[MAXN << 1];



int tmp[MAXN];

int f[MAXN][MAXN], g[MAXN];

int head[MAXN], siz[MAXN];

int N, cnt;



void sub( int &x, const int v ) { x = ( x < v ? x + mod - v : x - v ); }

void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }



void addEdge( const int from, const int to )

{

	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];

	head[from] = cnt;

}



void DFS( const int u, const int fa )

{

	f[u][1] = 1, siz[u] = 1;

	for( int i = head[u], v ; i ; i = Graph[i].nxt )

		if( ( v = Graph[i].to ) ^ fa )

		{

			DFS( v, u );

			for( int i = 0 ; i <= siz[u] + siz[v] ; i ++ ) tmp[i] = 0; 

			for( int j = siz[u] ; j ; j -- )

				for( int k = siz[v] ; ~ k ; k -- )

					add( tmp[j + k], 1ll * f[u][j] * f[v][k] % mod );

			siz[u] += siz[v];

			for( int i = 0 ; i <= siz[u] ; i ++ ) f[u][i] = tmp[i];

		}

	for( int i = 1 ; i <= siz[u] ; i ++ )

		sub( f[u][0], 1ll * f[u][i] * g[i] % mod );

}



int main()

{

	read( N );

	for( int i = 1, a, b ; i < N ; i ++ )

		read( a ), read( b ), addEdge( a, b ), addEdge( b, a );

	g[2] = 1;

	for( int i = 4 ; i <= N ; i += 2 )

		g[i] = 1ll * g[i - 2] * ( i - 1 ) % mod;

	DFS( 1, 0 );

	write( ( mod - f[1][0] ) % mod ), putchar( '\n' );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <vector>



using namespace std;



inline int gi()

{

	int f = 1, x = 0;

	char c = getchar();

	while (c < '0' || c > '9')

	{

		if (c == '-')

			f = -1;

		c = getchar();

	}

	while (c >= '0' && c <= '9')

	{

		x = x * 10 + c - '0';

		c = getchar();

	}

	return f * x;

}



const int mod = 1000000007;

vector<int> G[5005];

int f[5005][5005], g[5005], tmp[5005], n, sz[5005];



void dfs(int u, int fa)

{

	f[u][sz[u] = 1] = 1;

	for (auto v : G[u])

	{

		if (v != fa)

		{

			dfs(v, u);

			for (int i = 1; i <= sz[u] + sz[v]; i++) tmp[i] = 0;

			for (int i = 1; i <= sz[u]; i++)

			{

				for (int j = 0; j <= sz[v]; j++)

				{

					tmp[i + j] = (tmp[i + j] + 1ll * f[u][i] * f[v][j] % mod) % mod;

				}

			}

			for (int i = 1; i <= sz[u] + sz[v]; i++) f[u][i] = tmp[i];

			sz[u] = sz[u] + sz[v];

		}

	}

	for (int i = 2; i <= sz[u]; i = i + 2) f[u][0] = (f[u][0] + mod - 1ll * f[u][i] * g[i] % mod) % mod;

}



int main()

{

	g[0] = 1, n = gi();

	for (int i = 2; i <= n; i = i + 2) g[i] = 1ll * g[i - 2] * (i - 1) % mod;

	for (int i = 1; i < n; i++)

	{

		int x = gi(), y = gi();

		G[x].push_back(y), G[y].push_back(x);

	}

	dfs(1, 0);

	printf("%d\n", mod - f[1][0]);

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=5e3+51,MOD=1e9+7;

struct Edge{

	ll to,prev;

};

Edge ed[MAXN<<1];

ll nc,tot,from,to;

ll last[MAXN],sz[MAXN],f[MAXN],tmp[MAXN],dp[MAXN][MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline void addEdge(ll from,ll to)

{

	ed[++tot].prev=last[from];

	ed[tot].to=to;

	last[from]=tot;

}

inline void dfs(ll node,ll fa)

{

	ll p;

	sz[node]=dp[node][1]=1;

	for(register int i=last[node];i;i=ed[i].prev)

	{

		if(ed[i].to!=fa)

		{

			dfs(ed[i].to,node);

			for(register int j=0;j<=sz[node];j++)

			{

				tmp[j]=dp[node][j],dp[node][j]=0;

			}

			for(register int j=0;j<=sz[node];j++)

			{

				for(register int k=0;k<=sz[ed[i].to];k++)

				{

					p=(li)tmp[j]*dp[ed[i].to][k]%MOD;

					dp[node][j+k]=(dp[node][j+k]+p)%MOD;

				}

			}

			sz[node]+=sz[ed[i].to];

		}

	}

	for(register int i=0;i<=sz[node];i+=2)

	{

		dp[node][0]=(dp[node][0]+MOD-(li)dp[node][i]*f[i]%MOD)%MOD;

	}

}

int main()

{

	nc=read(),f[0]=1;

	for(register int i=0;i<nc-1;i++)

	{

		from=read(),to=read();

		addEdge(from,to),addEdge(to,from);

	}

	for(register int i=2;i<=nc;i++)

	{

		f[i]=(li)f[i-2]*(i-1)%MOD;

	}

	dfs(1,0),printf("%d\n",(MOD-dp[1][0])%MOD);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define per(i,a,b) for(int i=(a);i>=(b);i--)

#define REP(i,n) for(int i=(0);i<(n);i++)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef long long ll;



template<class T> inline void read(T &x){

	int f=0;x=0;char ch=getchar();

	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');

	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';

	if(f)x=-x;

}



const int N=5005,mod=1e9+7,inv2=(mod+1)/2;

int f[N][N],fac[N],rev[N],g[N],sz[N],t[N],n,x,y;

vi e[N];



int power(int x,int p){

	int res=1;

	for(;p;p>>=1,x=(ll)x*x%mod)

		if(p&1)res=(ll)res*x%mod;

	return res;

}



void dfs(int u,int fa){

	f[u][1]=sz[u]=1;

	for(auto v:e[u])

		if(v!=fa){

			dfs(v,u);

			fill(g,g+sz[u]+sz[v]+1,0);

			rep(a,1,sz[u])rep(b,0,sz[v])

				g[a+b]=(g[a+b]+(ll)f[u][a]*f[v][b])%mod;

			sz[u]+=sz[v];

			rep(a,1,sz[u])f[u][a]=g[a];

		}

	int sum=0;

	rep(i,1,sz[u])

		if(i%2==0&&f[u][i])

			sum=(sum+(ll)f[u][i]*t[i])%mod;

	f[u][0]=mod-sum;

}



int main(){

	read(n);

	fac[0]=1;

	rep(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;

	rev[n]=power(fac[n],mod-2);

	per(i,n,1)rev[i-1]=(ll)rev[i]*i%mod;

	rep(i,1,n)if(i%2==0)

		t[i]=(ll)fac[i]*rev[i/2]%mod*power(inv2,i/2)%mod;

	rep(i,1,n-1){

		read(x),read(y);

		e[x].pb(y),e[y].pb(x);

	}

	dfs(1,0);

	printf("%d\n",(mod-f[1][0])%mod);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=5e3+51,MOD=1e9+7;

struct Edge{

	ll to,prev;

};

Edge ed[MAXN<<1];

ll nc,tot,from,to;

ll last[MAXN],sz[MAXN],f[MAXN],tmp[MAXN],dp[MAXN][MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline void addEdge(ll from,ll to)

{

	ed[++tot].prev=last[from];

	ed[tot].to=to;

	last[from]=tot;

}

inline void dfs(ll node,ll fa)

{

	ll p;

	sz[node]=dp[node][1]=1;

	for(register int i=last[node];i;i=ed[i].prev)

	{

		if(ed[i].to!=fa)

		{

			dfs(ed[i].to,node);

			for(register int j=0;j<=sz[node];j++)

			{

				tmp[j]=dp[node][j],dp[node][j]=0;

			}

			for(register int j=0;j<=sz[node];j++)

			{

				for(register int k=0;k<=sz[ed[i].to];k++)

				{

					p=(li)tmp[j]*dp[ed[i].to][k]%MOD;

					dp[node][j+k]=(dp[node][j+k]+p)%MOD;

				}

			}

			sz[node]+=sz[ed[i].to];

		}

	}

	for(register int i=0;i<=sz[node];i+=2)

	{

		dp[node][0]=(dp[node][0]+MOD-(li)dp[node][i]*f[i]%MOD)%MOD;

	}

}

int main()

{

	nc=read(),f[0]=1;

	for(register int i=0;i<nc-1;i++)

	{

		from=read(),to=read();

		addEdge(from,to),addEdge(to,from);

	}

	for(register int i=2;i<=nc;i++)

	{

		f[i]=(li)f[i-2]*(i-1)%MOD;

	}

	dfs(1,0),printf("%d\n",(MOD-dp[1][0])%MOD);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define re register

using namespace std;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=5000+10;

const int mod=1e9+7;



struct edge { int v,nxt; } e[N<<1];

int head[N];



inline void addEdge(int u,int v) {

    static int e_cnt=0;

    e[++e_cnt]=(edge){v,head[u]},head[u]=e_cnt;

}



int n,sz[N];

int f[N][N],g[N],tmp[N];



inline void dfs(int u,int fa) {

    sz[u]=f[u][1]=1;

    for (re int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v; if (v==fa) continue;

        dfs(v,u);

        for (re int j=1;j<=sz[u]+sz[v];++j) tmp[j]=0;

        for (re int j=1;j<=sz[u];++j)

            for (re int k=0;k<=sz[v];++k)

                tmp[j+k]=(tmp[j+k]+1ll*f[u][j]*f[v][k])%mod;

        sz[u]+=sz[v];

        for (re int j=1;j<=sz[u];++j) f[u][j]=tmp[j];

    }

    for (re int i=2;i<=sz[u];i+=2)

        f[u][0]=(f[u][0]-1ll*f[u][i]*g[i]%mod+mod)%mod;

}



int main() {

    n=read();

    for (re int i=1;i<n;++i) {

        int u=read(),v=read();

        addEdge(u,v),addEdge(v,u);

    }

    g[0]=1;

    for (re int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;

    dfs(1,0); printf("%d\n",mod-f[1][0]);

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)



inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}



const int N(5010), Mod(1e9 + 7);

struct edge { int next, to; } e[N << 1];

int head[N], e_num, f[N][N], g[N], size[N], n;

inline void add_edge(int from, int to)

{

	e[++e_num] = (edge) {head[from], to};

	head[from] = e_num;

}



void dfs(int x, int fa)

{

	static int tmp[N];

	size[x] = 1; int *fx = f[x]; fx[1] = 1;

	for (int i = head[x]; i; i = e[i].next)

	{

		int to = e[i].to; if (to == fa) continue;

		dfs(to, x);

		for (int j = 0; j <= size[x]; j++)

			for (int k = 0; k <= size[to]; k++)

				tmp[j + k] = (tmp[j + k] + 1ll * fx[j] * f[to][k]) % Mod;

		size[x] += size[to], std::copy(tmp + 1, tmp + size[x] + 1, fx + 1);

		std::fill(tmp + 1, tmp + size[x] + 1, 0);

	}

	fx[0] = 0;

	for (int i = 1; i <= size[x]; i++)

		fx[0] = (fx[0] - 1ll * fx[i] * g[i] % Mod + Mod) % Mod;

}



int main()

{

	n = read(), g[0] = 1;

	for (int i = 1, a, b; i < n; i++)

		a = read(), b = read(), add_edge(a, b), add_edge(b, a);

	for (int i = 2; i <= n; i += 2) g[i] = 1ll * g[i - 2] * (i - 1) % Mod;

	dfs(1, 1); printf("%d\n", Mod - f[1][0]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

typedef pair<int,int> pii;

#define mp make_pair

inline int gi()

{

	int f=1,sum=0;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=110;

int n,x,D,p[N],v[N],id[N];

ll m[N],f[N*N*N];

void upt(ll m,int val){for(int i=n*n*n;i>=val;i--)f[i]=min(f[i],f[i-val]+m);}

bool cmp(int x,int y){return 1ll*m[y]*v[x]>1ll*m[x]*v[y];}

int main()

{

	n=gi();x=gi();D=gi();m[1]=gi();

	for(int i=2;i<=n;i++){m[i]=gi();p[i]=gi();}

	for(int i=1;i<=n;i++)v[i]=1,id[i]=i;

	for(int i=n;i>1;i--)m[p[i]]+=m[i],v[p[i]]+=v[i];

	memset(f,63,sizeof(f));f[0]=0;//package

	for(int i=1;i<=n;i++)

	{

		int lim=1,ret=(i==1)?n:min(n,D);

		while(ret>=lim)

		{

			ret-=lim;upt(1ll*m[i]*lim,1ll*lim*v[i]);lim<<=1;

		}

		upt(1ll*m[i]*ret,1ll*ret*v[i]);

	}

	int ans=0;sort(id+1,id+n+1,cmp);

	for(int i=0;i<=n*n*n;i++)

		if(f[i]<=x)

		{

			int res=x-f[i],sum=i;

			for(int j=1;j<=n;j++)

			{

				int del=(id[j]==1)?res/m[1]:min(max(0ll,(ll)D-n),res/m[id[j]]);

				sum+=v[id[j]]*del;

				res-=del*m[id[j]];

			}

			ans=max(ans,sum);

		}

	printf("%d\n",ans);

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

int n,x,d,mx,k;

int siz[55],fa[55],a[55];

ll ans,c[55],f[55*55*55];

int main(){

	cin>>n>>x>>d>>c[1]; mx=n*n*n,k=min(n,d); memset(f,0x3f,sizeof(f)); f[0]=0;

	for(int i=2;i<=n;++i) cin>>c[i]>>fa[i];

	for(int i=n;i>=1;--i) siz[i]++,siz[fa[i]]+=siz[i],c[fa[i]]+=c[i];

	for(int i=1;i<=n;++i) for(int j=1;j<=k;++j) for(int s=mx;s>=siz[i];--s) f[s]=min(f[s],f[s-siz[i]]+c[i]);

	for(int i=1;i<=n;++i) a[i]=i;

	sort(a+1,a+n+1,[](int x,int y){return c[x]*siz[y]<c[y]*siz[x];});

	for(int i=0;i<=mx;++i) if(f[i]<=x){

		ll tmp=i,las=x-f[i];

		for(int j=1;j<=n&&a[j]>1;++j){

			ll now=min(d-k+0ll,las/c[a[j]]);

			las-=c[a[j]]*now,tmp+=now*siz[a[j]]; 

		}

		tmp+=las/c[1]*siz[1];

		ans=max(ans,tmp);

	}

	cout<<ans<<endl;

	return 0;

}

// Fastest known solution for this problem: