Paths on the board

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

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

Output

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

Examples