La gran noria Cosmo Clock 21 es un símbolo de Yokohama y embellece la vista nocturna de la ciudad. La ciudad ICPC también quiere algo parecido.
La ciudad ICPC planea construir una noria iluminada con un número par de cabinas. Todas las cabinas deben pintarse con uno de los colores del conjunto dado de colores candidatos. La iluminación se planea así:
Todas las cabinas se agrupan en parejas; cada cabina pertenece a una única pareja.
Solo dos cabinas del mismo color pueden formar una pareja.
Las cabinas emparejadas se conectan mediante una línea LED recta para iluminar la noria.
Ninguna pareja de líneas LED se cruza al mirar desde el frente.
Un coloreado de las cabinas es adecuado si permite al menos una forma de emparejarlas que cumpla el plan de iluminación.
Figura C.1. Norias con coloreados adecuados (izquierda) y no adecuados (derecha)
Dados el número de cabinas y el de colores candidatos, cuenta los coloreados adecuados de las cabinas. Como la noria gira, dos coloreados se consideran iguales si coinciden tras alguna rotación. Dos coloreados que solo coinciden al mirar desde lados opuestos se consideran distintos.
Entrada
La entrada consta de un único caso de prueba con el siguiente formato.
$$n\quad k$$
$n$ y $k$ son enteros entre $1$ y $3\times10^6$, ambos inclusive. El número de cabinas y el de colores candidatos son $2n$ y $k$, respectivamente.
Salida
Imprime el número de coloreados adecuados de las cabinas módulo $998\,244\,353=2^{23}\times7\times17+1$, que es un número primo.
Ejemplos
Entrada 1
3 2
Salida 1
6
Entrada 2
5 3
Salida 2
372
Entrada 3
2023 1126
Salida 3
900119621
Nota
Para la entrada de ejemplo 1, hay seis coloreados adecuados, mostrados en la figura siguiente.
Figura C.2. Coloreados adecuados para $n=3$ y $k=2$