eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шляхи на дошці

Шляхи на дошці

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Розглянемо нескінченну клітчату дошку.

Назвемо шляхом із одній клітинки в іншу послідовність клітинок, у яких кожні дві клітинки, що йдуть підряд, мають сусідні сторони. Довжина шляху — це кількість клітинок у ньому, не рахуючи початкову.

Назвемо шлях простим, якщо у ньому не зустрічається двох однакових клітинок.

Зафіксуємо якусь клітинку на дошці. Скільки існує простих шляхів заданої довжини, які починаються у цій клітинці?

Вхідні дані

У першому рядку вхідного файлу задано ціле число n (0n22).

Вихідні дані

У першому рядку вихідного файлу виведіть одне число — кількість шляхів довжини n з цієї клітинки.

Приклад

Вхідні дані #1
0
Вихідні дані #1
1
Автор Сергій Копеліович
Джерело Зимова Школа, Харків 2011, День 5