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