e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

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

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

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

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

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

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

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

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

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