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