103. Три единицы подряд

Не решаласьЛёгкая

По данному числу N N определите количество последовательностей из нулей и единиц длины N N , в которых никакие три единицы не стоят рядом.

Формат ввода

Во входном файле написано натуральное число N N , не превосходящее 35 35 .

Формат вывода

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2 31 − 1 2^{31}-1 .

Ограничения

Ограничение времени
1 с
Ограничение памяти
64 МБ

Примеры

Пример 1

Ввод
1
Вывод
2

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти