Tower of Happiness

Problem description

The tower of happiness is located in the garden of effort. Happiness is waiting for you in the top chamber of the tower. The stairs that lead you to the chamber has N steps and you are allowed to climb up one or two steps from your current location. The door of the chamber will be open only if you could climb the steps in a secret combination. Of course, finding this secret combination is a matter of chance. For instance, you may choose one of the three ways to climb a three-step stairs: 0 1 2 3, or 0 1 3, or 0 2 3.

Make a program to determine how many different ways you can climb up the tower of happiness when you are given the number of steps. You must start from the ground which is step 0. The higher the tower is, the smaller the chance of catching the happiness gets.

Input

There is a single integer N on the first line of input (1 ≤ N ≤ 90).

Output

Number of different ways to the tower of happiness.

Example