Задача №2993. Последовательности из 0 и 1 без двух единиц и двоек подряд

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд и двух двоек подряд. Гарантируется, что ответ не превосходит 231-1.

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

Вводится натуральное число.

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

Выведите ответ на задачу.

Примеры
Входные данные
2
Выходные данные
7
Сдать: для сдачи задач необходимо войти в систему