Задачи
Взрывоопасные контейнеры
Взрывоопасные контейнеры
Все контейнеры в мире делятся на две категории — с тротилом и без. Только глупец поставит ящик с тротилом на другой ящик с тротилом. Поскольку вы не глупец (хм…), вы точно знаете, что тротил взрывается, особенно, если на нем стоит еще один ящик с тротилом. Вы находитесь в комнате, в которой находятся ящики обоих видов в гигантском количестве. Вдруг в комнате из люка появляется подъемник. Он сбоит. Он вознамерился построить башню из n ящиков. Для того, чтобы оценить ваши шансы на выживание, вам надо посчитать количество исходов, при которых ничего не взорвется.
Кстати, а что такой здравомыслящий человек, как вы, делает в комнате с кучей тротила?
Входные данные
Одно число n~(1 \le n < 45).
Выходные данные
Выведите количество хороших исходов.
Пример
Входные данные #1
1
Выходные данные #1
2
Входные данные #2
2
Выходные данные #2
3