京都大学にはシンボルツリーの立派なクスノキがあります。
K君はこのクスノキに感銘を受け、クスノキを \(N\) 頂点の根付き木として模写しました。
木の各頂点には \(1,2,\dots,N\) の番号が付いており、木の根は頂点 \(1\) であり、 \(i\) 本目の辺は頂点 \(u_i\) と頂点 \(v_i\) とを結びます。
ただ木を模写しただけではつまらないと考えたK君は、以下の 条件 を満たすように、木の各頂点に非負整数を書き込みます。
条件
木の頂点への整数の書き込み方としてありうるものの数を \(998244353\) で割った余りを求めてください。
ただし、木の頂点への整数の書き込み方は、ある頂点が存在してそこに書き込まれた整数が異なる、またその時に限り区別されます。
\(1\) 行目に整数 \(N,K\) が空白区切りで与えられる。 ( \(2 \leq N \leq 3000, 1 \leq K \leq 10^9\) )
続く \(N-1\) 行のうち \(i\) 行目には、木の辺を表す整数 \(u_i,v_i\) が空白区切りで与えられる。
部分点: \(N=K\) のケースにすべて正答すると \(1\) 点が得られる。
答えとなる整数を \(998244353\) で割った余りを出力してください。
5 11 21 33 43 5
10
16 1615 1415 117 1014 24 614 165 31 512 115 72 913 105 149 68 1
623173536
\(1\) つ目のサンプルについて、条件を満たす頂点 \(1,2,3,4,5\) への整数の書き込み方は以下の \(10\) 通りです。