P4727 [HNOI2009] Counting Graph Isomorphism Classes

When students run into a hard problem, they often say, “How can this be done? Isn’t this an NP problem?”, or “You can only search; this has already been proved to be an NP problem.” However, you should know that what most people call an NP problem in such cases actually refers to an NPC problem. Many people have not truly understood the two basic concepts: NP problems and NPC problems. In fact, an NP problem is not the kind of problem that “can only be solved by searching”; NPC problems are. Long ago, there was an old legend: there is a famous question, namely whether $P$ equals $NP$. In the legend, whoever proves or disproves this statement will obtain happiness. Here, $P$ refers to the set of problems that can be solved in polynomial time. $NP$ refers to the set of problems whose solutions can be verified in polynomial time. Clearly, $P$ is a subset of $NP$, because any problem solvable in polynomial time must also be verifiable in polynomial time. So far, no one has obtained happiness because of this statement. However, there is a general trend: people commonly believe that $P=NP$ does not hold. That is, most people believe that there exists at least one NP problem that cannot have a polynomial-time algorithm. People are so convinced that $P \neq NP$ for a reason: during the study of NP problems, researchers found a very special class of NP problems called NP-complete problems, i.e., the so-called NPC problems. It is precisely because NPC problems exist that people believe $P \neq NP$. After the concept of NPC was proposed, almost all “natural” hard problems were eventually proved to be NPC problems, with only three exceptions: - Linear programming; - Graph isomorphism; - Primality testing and integer factorization.

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!

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

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).

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