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

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

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

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

Вхідні дані

У першому рядку задано ціле число n (0 ≤ n ≤ 22).

Вихідні дані

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