Розглянемо строфу віршованого тексту, яка складається з \textbf{n} рядків. У ній всі рядки діляться на декілька класів, всередині кожного з яких рядки римуються між собою. У даній задачі будемо розглядати лише такі строфи, у яких кожен рядок римується хоча б з одним іншим. Наприклад, для катренів (чотиривіршів) є чотири можливі схеми римування, які задовольняють умовам попереднього абзацу. Це схеми \textbf{AABB}, \textbf{ABAB}, \textbf{ABBA} і \textbf{AAAA}. Для заданого розміри строфи порахуйте кількість різних римованих схем. \InputFile У вхідному файлі міститься ціле додатнє число \textbf{n}, яке не перевищує \textbf{26}. \OutputFile У вихідний файл виведіть кількість схем римування, які можна застосувати до \textbf{n}-віршів.