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

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

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

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

Одно число $n (0 \leq n \leq 45)$ .

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

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Отправки 4K

Коэффициент принятия 48 %