Ще задовго до того, як Шарик знайшов розумну книжку, загублену Пєчкіним, коли він лише розпочинав свої експерименти з розпилювання шахових дошок, коли ще на шаховій дошці білі поля були білими, а чорні – чорними, він задав одну зі своїх перших задачок Матроскіну.
"Скільки різних послідовностей довжини n можна скласти з клітинок розпилених шахових дошок, якщо в жодній із послідованостей ніякі три білих поля не повинні йти підряд"?
Матроскін так і не розв'язав ще цю задачку, так что ваше завдання допомогти йому.
Довжина послідовності n (n ≤ 64).
Вивести кількість вказаних послідовностей.