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