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