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

Простая задачка Шарика

Простая задачка Шарика

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

Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

"Сколько разных последовательностей длины n можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд"?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

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

Длина последовательности n (n64).

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

Вывести количество указанных последовательностей.

Пример

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