Петро та Василь грають у чергову цікаву гру. У них є аркуш паперу, на якому зображено n кружечків, помічених числами від 1 до n. Учасники по черезі малюють стрілочки, які з'єднують кружечки. При цьому стрілочку з кружечка a у кружечок b дозволено проводити, якщо викпонано дві умови:

1. ще немає стрілочки з a в b;
2. не можна дійти по стрілочкам з b в a.

Наприклад, у позиції зліва можна поставити одну з трьох стрілочок (як показано справа).

Проиграє той, хто не може зробити хід.

Петро вирішив написати програму, яка гратиме у цю гру. Для цього він хоче спочатку порахувати, скільки різних позицій може отриматись на аркуші.

Навведемо усі 25 позицій з умови.

Вхідні дані

Одне ціле число n (1 ≤ n ≤ 100).

Вихідні дані

Виведіть кількість можливих позицій без ведучих нулів.