При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
определить количество возможных типов безопасных стопок.
Входные данные
Одно число 1 ≤ N ≤ 20.
Выходные данные
Одно число — количество безопасных вариантов формирования стопки.
Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
3
|