서로 겹치지 않는 LIS

시간 제한2초메모리 제한512 MB

요약

n개 원소의 순열 가운데 LIS 길이와 같은 서로 겹치지 않는 증가 부분수열이 두 개 있는 순열의 개수를 998244353으로 나눈 나머지로 구합니다.

문제

순열의 LIS는 가장 긴 증가하는 부분 수열의 길이이다.

길이가 LIS와 같은 증가하는 부분 수열을 두 개 찾을 수 있고, 이 두 부분 수열이 원소를 하나도 공유하지 않으면 그 순열은 좋은 순열이다.

정수 $n$ 이 주어지면 $n$ 개의 원소로 이루어진 좋은 순열의 개수를 구하라. 답이 클 수 있으므로 $998244353$ 으로 나눈 나머지를 출력한다.

첫째 줄에 원소의 개수를 나타내는 정수 $n$ ( $1 \le n \le 75$ )이 주어진다.

좋은 순열의 개수를 $998244353$ 으로 나눈 나머지를 정수 하나로 출력한다.