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

• не можна ставити поспіль три клітини з тваринами одного виду.

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

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

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

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

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

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

5

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

16