graph g;
ll n,c,d;
int a[2d3],b[2d3];
Mint e[2d3][7d3],z;
void f(int i,int p){
	e[i][3..d+2]=1;
	rep[g.edge[i]](j,g.es[i]){
		if(j!=p){
			f(j,i);
			rep(k,d)e[i][k+3]*=e[j][k]+e[j][k+6];
		}
	}
}
{
	rd(n,c,(a,b)(n-1));
	g.setEdge(n+1,n-1,a,b);
	d=min(c,6d3);
	f(1,0);
	z=(c-d)*e[1][3d3];
	z+=e[1][3..d+2];
	wt(z);
}