2143: 순열 가지고 놀기
[만든사람 : 10hour]
문제 설명
얼마 전 누리는 구간 $[1..n]$의 정수가 한 번씩 들어가는 길이 $n$의 순열 $P$를 선물로 받았다. 누리는 $n!$ 개의 순열로 무엇을 할지 고민하던 중 양질의 순열의 수 $S(n)$ 을 구하기로 하였다.
어떤 순열의 $LIS$는 그 순열에서 만들 수 있는 가장 긴 증가하는 부분수열의 길이를 의미한다.
예를들어, 어떤 순열 $[3, 1, 5, 2, 4]$의 경우 부분수열 $[1, 2, 4]$ 이 가장 긴 증가하는 부분수열이고, 이때 $LIS=3$이다.
한 순열이 양질의 순열이라 함은, 그 순열 안에서 길이가 $LIS$와 같은 증가하는 부분수열을 겹치지 않게 2개 이상 찾을 수 있음을 의미한다. 겹치지 않게 라는 말은, 두 부분수열이 공유하는 원소가 없다는 것을 의미한다.
길이가 $n$인 모든 순열 $P$에 대해, $S(n)$ 양질의 순열 $P$의 개수이다.
누리를 위해 $S(n)$을 대신 구해주자. 단, 답이 매우 커질 수 있으므로 $998244353$으로 나눈 나머지를 대신 출력한다.
어떤 순열의 $LIS$는 그 순열에서 만들 수 있는 가장 긴 증가하는 부분수열의 길이를 의미한다.
예를들어, 어떤 순열 $[3, 1, 5, 2, 4]$의 경우 부분수열 $[1, 2, 4]$ 이 가장 긴 증가하는 부분수열이고, 이때 $LIS=3$이다.
한 순열이 양질의 순열이라 함은, 그 순열 안에서 길이가 $LIS$와 같은 증가하는 부분수열을 겹치지 않게 2개 이상 찾을 수 있음을 의미한다. 겹치지 않게 라는 말은, 두 부분수열이 공유하는 원소가 없다는 것을 의미한다.
길이가 $n$인 모든 순열 $P$에 대해, $S(n)$ 양질의 순열 $P$의 개수이다.
누리를 위해 $S(n)$을 대신 구해주자. 단, 답이 매우 커질 수 있으므로 $998244353$으로 나눈 나머지를 대신 출력한다.
입력 설명
첫 번째 줄에 자연수 $n$이 입력된다. $(1 \leq n \leq 75)$
출력 설명
첫 번째 줄에 $S(n) \mod 998244353$을 출력한다.
입력 예시 Copy
6
출력 예시 Copy
132