Задачи
Пути на доске
Пути на доске
Рассмотрим бесконечную клетчатую доску.
Назовём \textit{путём} из одной клетки в другую последовательность клеток, в которой каждые две идущие подряд клетки являются соседними по стороне. Длина пути --- это количество клеток в нём, не считая начальную.
Назовём путь \textit{простым}, если в нём не встречается двух одинаковых клеток.
Зафиксируем какую-то клетку на доске. Сколько существует простых путей заданной длины, начинающихся в этой клетке?
\InputFile
В первой строке входного файла задано целое число \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{22}).
\OutputFile
В первой строке выходного файла выведите одно число --- количество путей длины \textbf{n} из этой клетки.
Входные данные #1
0
Выходные данные #1
1