Ще задовго до того, як Шарик знайшов розумну книжку, загублену Пєчкіним, коли він лише розпочинав свої експерименти з розпилювання шахових дошок, коли ще на шаховій дошці білі поля були білими, а чорні – чорними, він задав одну зі своїх перших задачок Матроскіну.

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

Матроскін так і не розв'язав ще цю задачку, так что ваше завдання допомогти йому.

Вхідні дані

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

Вихідні дані

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