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: \begin{enumerate} \item The graph contains exactly \textbf{N} vertices and \textbf{N−1} edges. \item Exactly one vertex has no entering edges. \item The graph contains no directed cycles. \end{enumerate} 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 \textbf{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 \textbf{N}, you are to find the number of sheets that Vasya's dad has to stock up. \InputFile Input contains the single integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{50}). \OutputFile Output the number of "beautiful" graphs with \textbf{N} vertices.