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

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

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

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

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

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

Примеры