Vasya's Dad#4967

Vasya's Dad

1 second

64 megabytes

Hard

Vasya’s dad is good at maths. Lately, his favorite objects have been "beautiful" directed graphs. Dad calls a graph "beautiful" if all the following conditions are true:

The graph contains exactly $N$ vertices and $N - 1$ N - 1 edges.
Exactly one vertex has no entering edges.
The graph contains no directed cycles.

Dad calls two "beautiful" graphs isomorphic if the vertices of the first graph can be renumbered in such a way that it turns into the second one.

Dad picks an integer $N$ , stocks up on blank paper, and draws a "beautiful" graph on each sheet. He verifies that no two drawn graphs are isomorphic.

Given the number $N$ , you are to find the number of sheets that Vasya's dad has to stock up.

Input

Input contains the single integer $N$ ( $1 \leq N \leq 50$ 1 \leq N \leq 50).

Output

Output the number of "beautiful" graphs with $N$ vertices.

Examples

Example 1

Loading

N - 1

1 \leq N \leq 50