Competitions

# DSA Week 2

# 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** ≤ **n** ≤ **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.

Input example #1

1

Output example #1

1

Input example #3

3

Output example #3

2