시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB17151493.333%

문제

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.

예제 입력 1

6

예제 출력 1

132