Поганий підрядок

Знайдіть, скільки існує рядків заданої довжини $n$, які складаються лише з символів '$a$', '$b$' та '$c$', і які не містять підрядка "$ab$".

Вхідні дані

Єдине число $n(0\le n\le 45)$.

Вихідні дані

Виведіть кількість шуканих рядків.

Приклади