Задачі
Шляхи на дошці
Шляхи на дошці
Розглянемо нескінченну клітчату дошку.
Назвемо шляхом із одній клітинки в іншу послідовність клітинок, у яких кожні дві клітинки, що йдуть підряд, мають сусідні сторони. Довжина шляху — це кількість клітинок у ньому, не рахуючи початкову.
Назвемо шлях простим, якщо у ньому не зустрічається двох однакових клітинок.
Зафіксуємо якусь клітинку на дошці. Скільки існує простих шляхів заданої довжини, які починаються у цій клітинці?
Вхідні дані
У першому рядку вхідного файлу задано ціле число n (0 ≤ n ≤ 22).
Вихідні дані
У першому рядку вихідного файлу виведіть одне число — кількість шляхів довжини n з цієї клітинки.
Приклад
Вхідні дані #1
0
Вихідні дані #1
1