18461번 - Disjoint LIS 다국어

문제

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.

제한

힌트