eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Плохая подстрока

Плохая подстрока

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Найдите, сколько существует строк заданной длины n, состоящих только из символов 'a', 'b' и 'c', и не содержащих подстроки "ab".

Входные данные

Одно число n~(0 \le n \le 45).

Выходные данные

Выведите количество искомых строк.

Пример

Входные данные #1
1
Выходные данные #1
3
Входные данные #2
3
Выходные данные #2
21