Background

When students encounter a difficult problem, they often say, "How can this be done? Isn't this an NP problem?" or "This can only be solved by searching; it has been proven to be an NP problem." However, you should be clear that what most people refer to as NP problems are actually NPC problems. Many people do not truly grasp the fundamental concepts of NP and NPC problems. In fact, NP problems are not those that can only be solved by searching; NPC problems are.

There is an ancient legend that a famous problem, whether P equals NP, has been around for a long time. Whoever proves or disproves this proposition will gain happiness. Here, P refers to the set of problems that can be solved in polynomial time, while NP refers to the set of problems that can be verified in polynomial time. Clearly, P is a subset of NP because problems that can be solved in polynomial time can certainly be verified in polynomial time.

So far, no one has gained happiness from this proposition. However, there is a general trend that people widely believe $P \neq$, i.e., most people believe that at least one NP problem exists that cannot be solved with a polynomial-time algorithm. The reason people are so convinced that $P \neq$ is due to the discovery of a very special type of NP problem called NP-complete problems, or NPC problems. It is the existence of NPC problems that makes people believe $P \neq$.

After the concept of NPC was introduced, most "natural" hard problems were eventually proven to be NPC problems, with only three exceptions:

• Linear programming problems;
• Graph isomorphism problems;
• Prime number determination and large number factorization problems.

Problem Description

After learning about the above situation, Xiao Xue believes that directly challenging the ultimate problem is still quite difficult, so he decides to start with simpler problems. Specifically, he has developed a strong interest in graph isomorphism problems. Graphs $A$ and $B$ are considered isomorphic if, after reassigning the vertices of graph $A$, the vertex set and edge set of graph $A$ can completely correspond to those of graph $B$.

Xiao Xue is now focused on how to determine whether two graphs are isomorphic, and he also wants to know how many pairwise non-isomorphic graphs with $N$ vertices there are. It is well-known that the maximum number of edges in a simple graph with $N$ vertices is $N*(N-1)/2$, so there are $2^{N*(N-1)/2}$ possible graphs with $N$ vertices. Clearly, many of these graphs are isomorphic. Xiao Xue wants to know how many different graphs there are if isomorphic graphs are counted as one. He has assigned this task to you, so solve it quickly before he figures it out!

Input Format

The data is read from the file input.txt, which contains only one non-negative integer $N$, representing the number of vertices in the graph, where $0 \leq N \leq 60$.

Output Format

The output file output.txt contains only one integer, representing the number of non-isomorphic graphs with $N$ vertices under the isomorphism sense. Since the answer may be very large, the final output is the result modulo $997$ ($997$ is a prime number).

Sample Input and Output

Input Sample #1

1

Output Sample #1

1

Input Sample #2

2

Output Sample #2

2

Input Sample #3

3

Output Sample #3

4

Input Sample #4

5

Output Sample #4

34

Input Sample #5

9

Output Sample #5

493

Notes

For $40\%$ of the data, $N \leq 20$.
For $100\%$ of the data, $0 \leq N \leq 60$.

见题面 Input 部分

见题面 Output 部分