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