When students encounter a difficult problem, they often say, "How do you solve this? Isn't this an NP problem?" or "This can only be solved by searching; it has already been proven to be an NP problem." However, you should be aware that what most people refer to as NP problems in these contexts are actually NPC (NP-complete) problems. Many people have not truly grasped the basic concepts of NP problems and NPC problems. In fact, NP problems are not necessarily problems that "can only be solved by searching"; NPC problems are.

A long time ago, there was an ancient legend: there is a famous problem, the P versus NP problem. Legend has it that whoever proves or disproves this proposition will find 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 a problem that can be solved in polynomial time must also be verifiable in polynomial time.

So far, no one has found happiness through this proposition. However, there is a general trend: it is widely believed that $P \neq NP$. That is, most people believe that there exists at least one NP problem for which no polynomial-time algorithm exists. There is a reason why people are so convinced that $P \neq NP$: in the process of studying NP problems, a very special class of NP problems called NP-complete problems, or NPC problems, was identified. It is precisely the existence of NPC problems that leads people to believe $P \neq NP$.

After the concept of NPC was proposed, the vast majority of "natural" difficult problems were eventually proven to be NPC problems, with only three exceptions:

• Linear programming;
• Graph isomorphism;
• Primality testing and integer factorization.

After learning about the above, Xiaoxue decided that challenging the ultimate problems directly was too difficult, so she decided to start with simpler problems. Specifically, she developed a keen interest in the graph isomorphism problem. Graph A and graph B are considered isomorphic if, after a certain relabeling of the vertices of graph A, the vertex set and edge set of graph A correspond exactly to those of graph B.

Xiaoxue is now focused on how to determine whether two graphs are isomorphic, and she also wants to know how many non-isomorphic graphs with $N$ vertices exist. As is well known, a simple graph with $N$ vertices has at most $N*(N-1)/2$ edges, meaning there are $2^{N*(N-1)/2}$ possible configurations for a graph with $N$ vertices. Obviously, many of these graphs are isomorphic. What Xiaoxue wants to know is: if isomorphic graphs are counted as one, how many distinct graphs are there? She has handed this task to you. Solve it quickly before she figures it out!

Input

A single non-negative integer $N$, representing the number of vertices in the graph, where $0 \le N \le 60$.

Output

Output a single integer representing the number of non-isomorphic graphs with $N$ vertices. Since the answer may be very large, output the result modulo 997 (997 is a prime number).

Examples

Input 1

1

Output 1

1

Input 2

2

Output 2

2

Input 3

3

Output 3

4

Input 4

5

Output 4

34

Input 5

9

Output 5

493

Subtasks

• 40%: $N \le 20$
• 100%: $N \le 60$