При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.
Входные данные
Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).
Выходные данные
Программа должна вывести одно число – количество способов составить безопасную стопку из
N контейнеров.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 |
7 |