Папа у Васи силён в математике. В последнее время папа заинтересовался такими объектами, как «красивые» ориентированные графы. «Красивым» он называет ориентированный граф, удовлетворяющий следующим условиям:

1. Граф содержит ровно N узлов и N − 1 дугу.
2. Ровно у одной вершины графа нет ни одной входящей дуги.
3. Граф не содержит ориентированных циклов.

Папа говорит, что два «красивых» графа изоморфны, если можно перенумеровать вершины первого графа таким образом, чтобы получился второй граф.

Папа выбирает целое число N, запасается чистой бумагой и рисует на каждом листе ровно по одному «красивому» графу. При этом он следит, чтобы никакие два из нарисованных им графов не были изоморфны.

Зная число N, найдите, каким количеством листов бумаги должен предусмотрительно запастись Васин папа.

В единственной строке расположено целое число N (1 ≤ N ≤ 50).

Выведите количество «красивых» графов с заданным числом вершин.