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

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

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

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

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

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

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

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

Примеры