18453번 - Graph Counting 다국어

Consider undirected graphs on 2n vertices with no loops and no multiple edges. We will say that a graph G is good if there is no perfect matching in G, but for any edge not in G, if we add it to G, the resulting graph will have a perfect matching.

Your goal is to calculate the number of different good graphs on 2n vertices modulo 998 244 353.

Two graphs are different if they are non-isomorphic, meaning that one graph can not be transformed into another by relabeling the vertices.

The first line of the input contains one integer n (1 ≤ n ≤ 500 000). Recall that 2n is the number of vertices in graph.

Print one integer: the number of different good graphs on 2n vertices modulo 998 244 353.

Graphs for 2n = 4: