Problems
Paths on the board
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.
Input example #1
0
Output example #1
1
Input example #2
1
Output example #2
4
Input example #3
2
Output example #3
12