eolymp
Competitions

9 Round Spiral. Round 1. Step 9.

Взрывоопасность 2

При переработке радиоактивных материалов образуются отходы двух видов - особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число всевозможных безопасных стопок.

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

В первой строке дано число 1N1000.

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

Выведите одно число - количество безопасных вариантов формирования стопки.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3
Output example #1
5