Graph Counting

Time limit5sMemory limit512 MB

Summary

Count, modulo 998244353, the non-isomorphic undirected graphs on 2n vertices that have no perfect matching but lose that property when any missing edge is added.

Level: Hard9 of 10
Topics: Combinatorics, Graph, Math, Number theory
Solved: No attempts yet

Problem

Consider undirected graphs on 2n vertices with no loops and no multiple edges. A graph G is good if G has no perfect matching, but adding any edge not in G to G produces a graph that has a perfect matching.

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 cannot be transformed into the other by relabeling the vertices.

Input

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

Output

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

Hint

Graphs for 2n = 4:

Examples2

Example 1
Input
```
2
```
Expected output
```
2
```
Example 2
Input
```
353535
```
Expected output
```
331835697
```