eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пути на доске

Пути на доске

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Рассмотрим бесконечную клетчатую доску.

Назовём путём из одной клетки в другую последовательность клеток, в которой каждые две идущие подряд клетки являются соседними по стороне. Длина пути — это количество клеток в нём, не считая начальную.

Назовём путь простым, если в нём не встречается двух одинаковых клеток.

Зафиксируем какую-то клетку на доске. Сколько существует простых путей заданной длины, начинающихся в этой клетке?

Входные данные

В первой строке входного файла задано целое число n (0n22).

Выходные данные

В первой строке выходного файла выведите одно число — количество путей длины n из этой клетки.

Пример

Входные данные #1
0
Выходные данные #1
1
Автор Сергей Копелиович
Источник Зимняя школа, Харьков 2011, День 5