Задача Дороги

Описание

Пра-пра-пра-правнук Фродо - Фридо, перерывая старые вещи, нашел дневник своего пра-пра-пра-прадедушки, в котором были описаны все его приключения. Через многие годы (хоббиты, как известно, живут долго), как мы знаем, он опубликует его, назвавшись автором. Однако в описываемые времена, он еще и не задумывался об этом. Этот дневник помог ему коротать время долгими зимними вечерами. Однако не только тем, что его было очень интересно читать. Дело в том, что в нем было одна глава, которую он даже не решился опубликовать - она была настолько интересной и захватывающей, что он испугался за психическое здоровье впечатлительных читателей. Она описывала пребывание Фродо в заключении. В ней говорилось, что Сарумян часто "навещал" Фродо в темнице, причем, по словам автора, это делалось отнюдь не из жалости, ненависти и прочих очевидных причин - просто Сарумяну не с кем было поговорить (разве с орками можно о чем-либо разговаривать?). В этих беседах в основном говорил Сарумян. Он часто жаловался на свою тяжелую жизнь (распростанение тьмы, знаете ли, весьма не простая работа), но чаще всего предвосхищал то время, когда тьма захватит все Средиземье. Иногда он пускался в весьма прагматичные рассуждения: как надо будет организовать управление, какие налоги ввести и т.д. И вот в один день Сарумян опять начал разглагольствовать: "Когда я захвачу все государства Средиземья, надо будет понастроить хороших дорог. Однако надо сделать это так, чтобы не было возможности создать сильное противодействие мне. Каждое из государств в отдельности не сможет достойно сопротивляться моему правлению, однако если несколько государств объединятся, то это может быть серьезной угрозой. А для того чтобы они объединились, необходимо, чтобы для каждого из этих государств можно было добраться до любого другого из них же по дорогам, напрямую, или через другие государства. Интересно, сколько же существует вариантов такого построения дорог, что никакое множество государств не сможет объединиться?" На этом месте Сарумян вспомнил, что ему надо сделать еще несколько тысяч орков и удалился. Естественно Фродо не обращал внимания на его болтовню, однако Фридо - математик с головы до ног - обратил внимание именно на это место. Он решил, что Сарумян смог бы построить не более одной дороги между каждой парой государств. А также из-за своей предусмотрительности (или глупости) он, конечно, построил бы однонаправленные дороги. "Интересно, а сколько же все-таки вариантов?" - подумал Фридо и стал считать... Это и послужило задержкой опубликования дневника - он не хотел печатать его, пока не посчитает. Он конечно же посчитал, но у него ушла на это вся молодость. Интересно, а успеете ли вы посчитать количество вариантов постройки дорог за 5 часов?

Формат входных данных

Во входном файле содержится целое число N - количество государств в Средиземье (1 <= N <= 80). Считайте, что изначально (перед постройкой) дорог нет - они были уничтожены во время войны.

Формат выходных данных

В выходной файл выведите одно целое число без ведущих нулей - количество вариантов постройки дорог.