Description

yww is going to start drawing.

There is a sheet of paper on the ground, and there are $n$ points on it.

yww wants to draw edges between the points. His way of drawing edges is very regular. Each time, he will hold the pen, choose a point, and draw an edge from this point $x$ to another point $y$, then draw an edge from $y$ to another point $z$, and so on, until he finally returns to point $x$. yww will do this process several times. Also, from start to finish, yww will never draw more than one edge between the same two points.

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

In one sentence: the number of unlabeled graphs on $n$ vertices such that every connected component has an Euler circuit.

Input Format

The first line contains an integer $n$.

Output Format

Output one integer.

4

3

5

7

Hint

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

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

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

Translated by ChatGPT 5