La Universidad de Kioto tiene un magnífico árbol simbólico como su árbol insignia.

Impresionado por este árbol simbólico, K-kun hizo una copia de él como un árbol enraizado con $N$ vértices.

Los vértices del árbol están etiquetados como $1, 2, \dots, N$, la raíz del árbol es el vértice $1$, y la $i$-ésima arista conecta los vértices $u_i$ y $v_i$.

Pensando que simplemente copiar el árbol sería poco interesante, K-kun escribe un número entero no negativo en cada vértice del árbol de modo que se satisfagan las siguientes condiciones:

Condiciones

• El número entero escrito en la raíz es $K$.
• Para cada vértice distinto de la raíz, el número entero escrito en ese vértice es, como máximo, el número entero escrito en su padre.

Encuentre el resto de dividir el número de formas posibles de escribir números enteros en los vértices del árbol entre $998244353$.

Dos formas de escribir números enteros en los vértices se consideran diferentes si y solo si existe algún vértice tal que el número entero escrito en ese vértice sea diferente.

Entrada

La primera línea contiene los enteros $N, K$ separados por espacios. ($2 \le N \le 3000, 1 \le K \le 10^9$)

Cada una de las siguientes $N - 1$ líneas contiene los enteros $u_i, v_i$ separados por espacios, representando una arista del árbol.

Salida

Imprima la respuesta módulo $998244353$.

Ejemplos

Entrada 1

5 1
1 2
1 3
3 4
3 5

Salida 1

10

Nota

Para el primer ejemplo, las siguientes 10 asignaciones de números enteros a los vértices 1, 2, 3, 4, 5 satisfacen las condiciones:

• 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

Entrada 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

Salida 2

623173536