Description

After learning the above, Xiaoxue felt that directly challenging the ultimate problem was still quite difficult, so he decided to start with simpler problems. Specifically, he became very interested in the graph isomorphism problem. Graph $A$ and graph $B$ are considered isomorphic if, after relabeling the vertices of graph $A$ in some way, the vertex set and edge set of $A$ correspond exactly one-to-one with those of $B$.

Xiaoxue is now focused on how to determine whether two graphs are isomorphic. At the same time, he also wants to know how many pairwise non-isomorphic graphs with $N$ vertices there are. It is well known that a simple graph with $N$ vertices has at most $N\times(N-1)/2$ edges, so there are $2^{N\times(N-1)/2}$ possible graphs with $N$ vertices. Clearly, many of these graphs are isomorphic. What Xiaoxue wants to know is: if we count isomorphic graphs as one, how many different graphs are there? He threw this task to you—solve it quickly before he figures it out!

Input Format

The input contains a non-negative integer $N$, representing the number of vertices of the graph, and $0 \leq N \leq 60$.

Output Format

Output one integer, representing the number of graphs with $N$ vertices that are non-isomorphic under isomorphism. Since the answer may be very large, output the final result $\bmod ~ 997$ ($997$ is a prime).

1

1

2

2

3

4

5

34

9

493

Hint

For $40\%$ of the testdata, $N \le 20$.
For $100\%$ of the testdata, $0 \le N \le 60$.

Translated by ChatGPT 5