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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади