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