eolymp
bolt
Try our new interface for solving problems
Problems

Paths on the board

Paths on the board

Time limit 1 second
Memory limit 256 MiB

Consider an infinite checkered board.

We call a path from one cell to another sequence of cells, in which every two consecutive cells are adjacent to the side. Path length - the number of cells in it, not counting the initial value.

We call the path simple if it does not meet two identical cells.

Fix the cells on the board. As there are simple ways of a given length, starting in the cage?

Input data

The first line of the input file is given an integer n (0n22).

Output data

The first line of the output file output a single number - the number of paths of length n from this cell.

Examples

Input example #1
0
Output example #1
1
Author Sergey Kopeliovich
Source Winter School, Kharkov, 2011, Day 5