Hay una caja etiquetada con cada número entero del 1 al $N$. Además, para cada número entero del 1 al $N$, hay $M$ bolas etiquetadas con ese número.
Estas $NM$ bolas se barajan y luego se distribuyen en las $N$ cajas, colocando exactamente $M$ bolas en cada caja.
Existen $\frac{(NM)!}{(M!)^N}$ formas posibles de colocar las bolas (si todas las bolas se consideran distinguibles), y todas estas disposiciones ocurren con igual probabilidad.
Usted realizará operaciones en estas cajas y bolas. Una operación consiste en los siguientes pasos:
- Elija una caja y colóquese frente a ella.
- Si no hay ninguna bola en esa caja, termine la operación.
- Elija cualquier bola de esa caja y deséchela fuera de la caja.
- Finalmente, colóquese frente a la caja cuya etiqueta coincida con la etiqueta de la bola desechada más recientemente y regrese al paso 2.
Defina su puntuación como el número de operaciones requeridas hasta que todas las $NM$ bolas hayan sido desechadas. Usted desea minimizar esta puntuación.
Encuentre el valor esperado de la puntuación cuando actúa de manera óptima, módulo 998244353.
Entrada
La primera línea contiene $N$ y $M$ en este orden, separados por espacios. ($1 \le N \le 10^5$, $1 \le M \le 100$)
Salida
Imprima la respuesta.
Ejemplos
Entrada 1
2 2
Salida 1
166374060
Entrada 2
3 1
Salida 2
831870296
Entrada 3
100000 100
Salida 3
402978825
Nota
Para el primer ejemplo, las posibles disposiciones de las bolas y las formas óptimas de operar correspondientes son las siguientes:
Poner dos bolas etiquetadas con 1 en la caja 1, y dos bolas etiquetadas con 2 en la caja 2. (Probabilidad 1/6)
- En la primera operación, colóquese frente a la caja 1. Desde allí, saque una bola etiquetada con 1 y colóquese frente a la caja 1. Luego saque otra bola etiquetada con 1 y colóquese frente a la caja 1 nuevamente. En este punto, la caja 1 está vacía, así que termine la operación.
- En la segunda operación, colóquese frente a la caja 2. Desde allí, saque una bola etiquetada con 2 y colóquese frente a la caja 2. Luego saque otra bola etiquetada con 2 y colóquese frente a la caja 2 nuevamente. En este punto, la caja 2 está vacía, así que termine la operación.
- En este caso, la puntuación mínima alcanzable es 2.
Poner una bola etiquetada con 1 y una bola etiquetada con 2 en cada una de las cajas 1 y 2. (Probabilidad 2/3)
- En la primera operación, colóquese frente a la caja 1. Desde allí, saque una bola etiquetada con 1 y colóquese frente a la caja 1. Luego saque una bola etiquetada con 2 y colóquese frente a la caja 2. Luego saque una bola etiquetada con 2 y colóquese frente a la caja 2. Luego saque una bola etiquetada con 1 y colóquese frente a la caja 1. En este punto, la caja 1 está vacía, así que termine la operación.
- En este caso, la puntuación mínima alcanzable es 1.
Poner dos bolas etiquetadas con 2 en la caja 1, y dos bolas etiquetadas con 1 en la caja 2. (Probabilidad 1/6)
- En la primera operación, colóquese frente a la caja 1. Desde allí, saque una bola etiquetada con 2 y colóquese frente a la caja 2. Luego saque una bola etiquetada con 1 y colóquese frente a la caja 1. Luego saque una bola etiquetada con 2 y colóquese frente a la caja 2. Luego saque una bola etiquetada con 1 y colóquese frente a la caja 1. En este punto, la caja 1 está vacía, así que termine la operación.
- En este caso, la puntuación mínima alcanzable es 1.
En resumen, la puntuación mínima es 2 con probabilidad 1/6, y la puntuación mínima es 1 con probabilidad 5/6, por lo que el valor esperado de la puntuación total es 7/6. Por lo tanto, imprima 166374060, que representa este valor módulo 998244353.
Definición de valor esperado módulo 998244353
Se puede demostrar que el valor esperado a encontrar es siempre un número racional. Además, bajo las restricciones de este problema, si el valor esperado se escribe como una fracción irreducible $\frac{y}{x}$, se garantiza que $x$ no es divisible por 998244353.
En este caso, existe un único número entero $z$ entre 0 y 998244352, inclusive, que satisface $xz \equiv y \pmod{998244353}$. Imprima este $z$.