|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||9||8||6||85.714%|
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: