Вибухонебезпечніть 2

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

Вхідні дані

У першому рядку задано число 1 ≤ N ≤ 1000.

Вихідні дані

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

Приклади