Soit LIS la longueur de la plus longue sous-suite croissante d'une permutation.

Une permutation est dite bonne s'il est possible de trouver deux sous-suites croissantes de longueur LIS qui ne partagent aucun élément commun.

Étant donné $n$, trouvez le nombre de bonnes permutations avec $n$ éléments. Comme la réponse peut être grande, vous devez seulement la trouver modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 75$) : le nombre d'éléments.

Sortie

Affichez un entier : le nombre de bonnes permutations avec $n$ éléments, modulo $998\,244\,353$.

Exemples

Entrée 1

6

Sortie 1

132