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

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

Вхідні дані

Єдине число n (0 ≤ n≤ 45).

Вихідні дані

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