京都大学には、シンボルツリーとして壮大な木があります。 このシンボリックツリーに感銘を受けたK君は、それを模した $N$ 頂点の根付き木を作成しました。 この木の頂点には $1, 2, \dots, N$ のラベルが付けられており、根は頂点 $1$ です。また、$i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいます。

単に木をコピーするだけでは面白くないと考えたK君は、以下の条件を満たすように、木の各頂点に非負整数を書き込むことにしました。

• 根に書き込まれる整数は $K$ である。
• 根以外の各頂点について、その頂点に書き込まれる整数は、その親に書き込まれる整数以下である。

木の各頂点に整数を書き込む方法が何通りあるかを求め、その数を $998244353$ で割った余りを出力してください。 頂点への整数の書き込み方は、ある頂点において書き込まれている整数が異なる場合にのみ、異なる書き込み方であるとみなします。

入力

入力は以下の形式で与えられます。

$N$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\dots$ $u_{N-1}$ $v_{N-1}$

ここで、$2 \le N \le 3000, 1 \le K \le 10^9$ です。

出力

答えを $998244353$ で割った余りを出力してください。

入出力例

入力 1

5 1
1 2
1 3
3 4
3 5

出力 1

10

入力 2

16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1

出力 2

623173536

注記

最初の例について、頂点 $1, 2, 3, 4, 5$ への整数の割り当てとして、以下の10通りが条件を満たします。

• $1, 0, 0, 0, 0$
• $1, 0, 1, 0, 0$
• $1, 0, 1, 0, 1$
• $1, 0, 1, 1, 0$
• $1, 0, 1, 1, 1$
• $1, 1, 0, 0, 0$
• $1, 1, 1, 0, 0$
• $1, 1, 1, 0, 1$
• $1, 1, 1, 1, 0$
• $1, 1, 1, 1, 1$