Петро та Василь грають у чергову цікаву гру. У них є аркуш паперу, на якому зображено n кружечків, помічених числами від 1 до n. Учасники по черезі малюють стрілочки, які з'єднують кружечки. При цьому стрілочку з кружечка a у кружечок b дозволено проводити, якщо викпонано дві умови:
ще немає стрілочки з a в b;
не можна дійти по стрілочкам з b в a.
Наприклад, у позиції зліва можна поставити одну з трьох стрілочок (як показано справа).
Проиграє той, хто не може зробити хід.
Петро вирішив написати програму, яка гратиме у цю гру. Для цього він хоче спочатку порахувати, скільки різних позицій може отриматись на аркуші.
Навведемо усі 25 позицій з умови.
Одне ціле число n (1 ≤ n ≤ 100).
Виведіть кількість можливих позицій без ведучих нулів.