El salón de las canciones#13109

El salón de las canciones

1 segundo
256 megabytes

En una taberna tocan músicos. Al principio cada músico conoce exactamente una canción, y las canciones son todas distintas.

Después de la actuación de cada noche, el tabernero elige un músico de manera uniforme al azar entre los músicos y luego un músico de manera uniforme al azar entre los otros n - 1 músicos, de modo que b \ne a. El músico olvida la canción que conoce y aprende la canción que el músico conoce en ese momento. Todas las elecciones son independientes. Así, cada músico conoce siempre exactamente una canción, aunque varios músicos pueden conocer la misma canción.

Halle el valor esperado de la cantidad de canciones distintas que conocen los músicos después de noches.

Entrada

La única línea contiene dos enteros y (2 \le n \le 100, 0 \le k \le 10^{18}) — la cantidad de músicos y la cantidad de noches.

Salida

Imprima un entero. Se puede demostrar que el valor esperado es un número racional \frac{p}{q}, donde no es divisible entre . Imprima p \cdot q^{-1} \bmod 998\,244\,353, es decir, el entero tal que 0 \le x < 998\,244\,353 y x \cdot q \equiv p \pmod{998\,244\,353}.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Ejemplo 4

Loading
Loading

Nota

En el primer ejemplo, n = 4 y k = 2. Después de la primera noche dos de los cuatro músicos conocen la misma canción y cada uno de los otros dos conoce una canción propia, así que hay canciones. En la segunda noche, si es uno de los dos músicos que conocen una canción propia, esa canción se pierde y quedan canciones; en caso contrario quedan canciones. Cada uno de estos casos ocurre con probabilidad \frac{2}{4}, de modo que la cantidad esperada de canciones es \frac{1}{2} \cdot 2 + \frac{1}{2} \cdot 3 = \frac{5}{2}, y 499\,122\,179 \cdot 2 \equiv 5 \pmod{998\,244\,353}. La figura muestra una posible primera noche (a = 2, b = 1; cada círculo muestra la canción de un músico, los músicos están numerados arriba) y los dos tipos de resultados de la segunda noche; los números de abajo y de la derecha son las cantidades de canciones distintas.

En el segundo ejemplo, n = 6 y k = 1. En la primera noche el músico reemplaza su canción por otra distinta, así que se pierde exactamente una canción y quedan canciones.

En el tercer ejemplo, n = 2. Después de la primera noche ambos músicos conocen la misma canción y, a partir de entonces, se conoce exactamente canción.

En el cuarto ejemplo, k = 0, así que todavía se conocen las canciones.