eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Схемы рифмовки

Схемы рифмовки

Лимит времени 0.5 секунд
Лимит использования памяти 256 MiB

Рассмотрим строфу стихотворного текста, состоящую из n строчек. В ней все строчки делятся на несколько классов, внутри каждого из которых строки рифмуются между собой. В данной задаче будем рассматривать только такие строфы, в которых каждая строка рифмуется хотя бы с одной другой.

Например, для катренов (четверостиший) есть четыре возможных схемы рифмовки, удовлетворяющих условиям предыдущего абзаца. Это схемы AABB, ABAB, ABBA и AAAA.

Для заданного размера строфы сосчитайте количество различных рифмовых схем.

Входные данные

Во входном файле содержится целое положительное число n, не превосходящее 26.

Выходные данные

В выходной файл выведите количество схем рифмовки, применимых к n-стишиям.

Пример

Входные данные #1
4
Выходные данные #1
4
Автор Михаил Дворкин
Источник Зимняя школа, Харьков 2011, День 3