Disjoint LIS
시간 제한2초메모리 제한512 MB
최장 증가 부분수열을 서로 원소를 공유하지 않는 두 개의 증가 부분수열로 나타낼 수 있는 n개 원소 순열의 개수를 998244353으로 나눈 나머지를 구한다.
문제
Let the LIS of a permutation be the length of its longest increasing subsequence.
A permutation is good if it is possible to find two increasing subsequences of length LIS that do not share any common elements.
Given n, find the number of good permutations with n elements. As the answer may be large, you only need to find it modulo 998 244 353.
입력
The first line of input contains one integer n (1 ≤ n ≤ 75): the number of elements.
출력
Output one integer: the number of good permutations with n elements, modulo 998 244 353.