Paths on the board

Consider the infinite checkered board.

Let's call a path from one cell to another the sequence of cells, where each two consecutive cells are adjacent on the side. The length of the path is the number of cells in it, not counting the starting point.

The path is simple if it does not contain two identical cells.

Let's fix some cell on the board. How many simple paths exist with specified length that starts in this cell?

Input

One integer n (0 ≤ n ≤ 22).

Output

Print the number of simple paths of length n that starts from the given cell.

Examples