Sea LIS la longitud de la subsecuencia creciente más larga de una permutación.

Una permutación es buena si es posible encontrar dos subsecuencias crecientes de longitud LIS que no compartan ningún elemento en común.

Dado $n$, encuentre el número de permutaciones buenas con $n$ elementos. Como la respuesta puede ser grande, solo necesita encontrarla módulo $998\,244\,353$.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 75$): el número de elementos.

Salida

Imprima un entero: el número de permutaciones buenas con $n$ elementos, módulo $998\,244\,353$.

Ejemplos

Entrada 1

6

Salida 1

132