Counting Unlabeled Eulerian Graphs

You are given an integer n (with 1 ≤ n ≤ 5), which represents the number of vertices. Consider all simple (undirected and without multiple edges) graphs on n vertices that satisfy the following property: in every connected component, there exists an Eulerian circuit. Equivalently, every vertex of the graph has an even degree (note that an isolated vertex is considered to have degree 0, which is even).

Two graphs are considered isomorphic if there exists a permutation of vertices which transforms one graph into the other. In other words, they are essentially the same if one can be re‐labeled to obtain the other. Your task is to count the number of non–isomorphic graphs satisfying the property above. Since the answer might be very large, output it modulo \(998244353\).

Note: In this problem, each graph is built by a sequence of drawing operations that create cycles. In every such operation, one starts at a chosen vertex \(x\) and draws an edge to a different vertex \(y\), then from \(y\) to another vertex \(z\), and so on, eventually returning to \(x\). Throughout the drawing, no pair of vertices is connected by more than one edge. It can be proved that the graphs obtainable in this way are exactly the simple graphs in which every vertex has an even degree.

inputFormat

The input consists of a single integer:

n

where 1 ≤ n ≤ 5.

outputFormat

Output a single integer, the number of non–isomorphic graphs on n vertices in which every vertex has an even degree, modulo \(998244353\).

sample

1

1