ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1387. Папа у Васи

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Папа у Васи силён в математике. В последнее время папа заинтересовался такими объектами, как «красивые» ориентированные графы. «Красивым» он называет ориентированный граф, удовлетворяющий следующим условиям:
  1. Граф содержит ровно N узлов и N − 1 дугу.
  2. Ровно у одной вершины графа нет ни одной входящей дуги.
  3. Граф не содержит ориентированных циклов.
Папа говорит, что два «красивых» графа изоморфны, если можно перенумеровать вершины первого графа таким образом, чтобы получился второй граф.
Папа выбирает целое число N, запасается чистой бумагой и рисует на каждом листе ровно по одному «красивому» графу. При этом он следит, чтобы никакие два из нарисованных им графов не были изоморфны.
Зная число N, найдите, каким количеством листов бумаги должен предусмотрительно запастись Васин папа.

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
3
2
5
9
Автор задачи: Александр Ипатов
Источник задачи: Petrozavodsk summer training camp, August 2005.