Honeycomb

The bee can go in honeycomb as shown in the figure — with moves $1$ and $2$ from upper row and with move $3$ from the lower.

Input

The number of hexagons $n(1\le n\le 45)$ in the upper row. The lower row contains $1$ hexagon less.

Output

Print the number of ways to get from the first cell of the top row to the last cell of the same row.

Examples