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

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

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

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

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

Одно целое число n (0 ≤ n ≤ 22).

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

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