Схеми римування

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

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

Для заданого розміри строфи порахуйте кількість різних римованих схем.

Вхідні дані

У вхідному файлі міститься ціле додатнє число n, яке не перевищує 26.

Вихідні дані

У вихідний файл виведіть кількість схем римування, які можна застосувати до n-віршів.

Приклади