eolymp
bolt
Try our new interface for solving problems
Problems

Honeycomb

Honeycomb

Time limit 1 second
Memory limit 128 MiB

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 data

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

Output data

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

Examples

Input example #1
1
Output example #1
1
Input example #3
3
Output example #3
2