У зоомагазині потрібно розставити в один ряд кліток з тваринами. Тварини є двої видів (собаки і коти)

У ряд поміститься \(N\) кліток, але є одне обмеження:

• не можна ставити поруч дві клітки із собаками (інакше вони покусаються).

Визначте, скількома безпечними способами можна розставити \(N\) кліток у ряд.

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

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

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

Програма повинна вивести кількість безпечних способів розміщення \(N\) кліток в ряд.

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

5

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

13