eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Взрывоопасные контейнеры

Взрывоопасные контейнеры

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Все контейнеры в мире делятся на две категории — с тротилом и без. Только глупец поставит ящик с тротилом на другой ящик с тротилом. Поскольку вы не глупец (хм…), вы точно знаете, что тротил взрывается, особенно, если на нем стоит еще один ящик с тротилом. Вы находитесь в комнате, в которой находятся ящики обоих видов в гигантском количестве. Вдруг в комнате из люка появляется подъемник. Он сбоит. Он вознамерился построить башню из n ящиков. Для того, чтобы оценить ваши шансы на выживание, вам надо посчитать количество исходов, при которых ничего не взорвется.

Кстати, а что такой здравомыслящий человек, как вы, делает в комнате с кучей тротила?

Входные данные

Одно число n~(1 \le n < 45).

Выходные данные

Выведите количество хороших исходов.

Пример

Входные данные #1
1
Выходные данные #1
2
Входные данные #2
2
Выходные данные #2
3