eolymp
Змагання

October 7 - BMTK Programming School, High League

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

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

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
0
Вихідні дані #1
1
Вхідні дані #2
3
Вихідні дані #2
21
Вхідні дані #3
11
Вихідні дані #3
46368