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

Для заданої кількості контейнерів \(N\) визначте, скільки є способів скласти безпечну стопку.

Формат вхідних даних

Вхідний рядок містить натуральне число – кількість контейнерів \(N\) у стопці.

Формат вихідних даних

Програма має вивести одне число – кількість способів скласти безпечну стопку із \(N\) контейнерів.

Приклад вхідних даних

3

Приклад вихідних даних

7