eolymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

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

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

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

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
1
Выходные данные #1
2
Входные данные #2
2
Выходные данные #2
4
Входные данные #3
3
Выходные данные #3
7