Вибухонебезпечні контейнери

Усі контейнери у світі діляться на дві категорії — з тротилом і без. Лише дурень поставить ящик з тротилом на інший ящик з тротилом. Оскільки ви не дурень (хм…), ви точно знаєте, що тротил вибухає, особлив, якщо на ньому стоїть ще один ящик з тротилом. Ви знаходитесь у кімнаті, у якій знаходяться ящики обох видів у гігантській кількості. Раптом у кімнаті з люку з'являється підйомник. Він збоїть. Він має намір побудувати башту з $n$ ящиків. Для того, щоб оцінити ваші шанси на виживання, вам потрібно порахувати кількість випадків, при яких нічого не взірветься.

Да, до речі, а що така розсудлива людина, як ви, робить у кімнаті з купою тротилу?

Вхідні дані

У першому рядку знаходиться число $n(1\le n<45)$.

Вихідні дані

Виведіть одне число — кількість хороших випадків.

Приклади