D. Disjoint LIS
time limit per test
3 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

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$$$.

Input

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

Output

Output one integer: the number of good permutations with $$$n$$$ elements, modulo $$$998\,244\,353$$$.

Example
Input
6
Output
132