Тато у Васі
Васін тато захоплюється математикою і особливо цікавиться "красивими" орієнтованими графами. Він вважає граф "красивим", якщо він відповідає таким умовам:
Граф містить рівно N вузлів і N−1 дугу.
Лише одна вершина графа не має жодної вхідної дуги.
Граф не містить орієнтованих циклів.
Тато стверджує, що два "красивих" графи є ізоморфними, якщо можна перенумерувати вершини одного графа так, щоб отримати другий граф.
Він вибирає ціле число N, бере чистий папір і малює на кожному аркуші по одному "красивому" графу, стежачи за тим, щоб жодні два з намальованих графів не були ізоморфні.
Знаючи число N, визначте, скільки аркушів паперу потрібно підготувати Васіному татові.
Вхідні дані
У єдиному рядку задано ціле число N (1 ≤ N ≤ 50).
Вихідні дані
Виведіть кількість "красивих" графів із заданою кількістю вершин.