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

1. The graph contains exactly N vertices and N−1 edges.
2. Exactly one vertex has no entering edges.
3. The graph contains no directed cycles.

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

Dad picks an integer N, stocks up 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 contains the single integer N (1 ≤ N ≤ 50).

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