Problem Description

yww is about to start painting!

There is a sheet of paper on the ground with $n$ points on it.

yww will connect the points with edges. His method of connecting is very systematic. Each time, he will pick up his pen, select a point $x$, and connect it to another point $y$, then from $y$ to another point $z$, and so on, until he connects back to point $x$. yww will perform this process multiple times, and throughout, he will never connect two points with more than one edge.

yww wants to know how many fundamentally different graphs he can draw. Two graphs are considered fundamentally the same if there exists a permutation of points such that for both the original and the permuted graph, any two points either have no edge between them or have an edge in both graphs. You only need to output the answer modulo $998244353$.

In summary, the problem asks for the number of unlabeled graphs with $n$ points where each connected component has an Eulerian circuit.

Input Format

The first line contains a single number $n$.

Output Format

Output a single number.

Sample Input and Output

Sample Input #1

4

Sample Output #1

3

Sample Input #2

5

Sample Output #2

7

Notes/Hints

For $10\%$ of the data, $n \le 5$.

For $40\%$ of the data, $n \le 10$.

For $100\%$ of the data, $1 \le n \le 50$.

见题面 Input 部分

见题面 Output 部分