시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 10 9 7 87.500%

문제

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.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

353535

예제 출력 2

331835697

힌트

Graphs for 2n = 4: