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

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

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

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

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

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

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

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

Примеры