Disjoint LIS

Time limit2sMemory limit512 MB

Summary

Count the permutations of n elements that contain two disjoint increasing subsequences, each as long as the LIS, modulo 998244353.

Problem

The LIS of a permutation is the length of its longest increasing subsequence.

A permutation is good if two increasing subsequences of length equal to its LIS can be found that share no elements.

Given $n$ , count the good permutations of $n$ elements. The answer may be large, so output it modulo $998244353$ .

The first line contains one integer $n$ ( $1 \le n \le 75$ ): the number of elements.

Output one integer: the number of good permutations of $n$ elements, modulo $998244353$ .