Time limit 1000/1000/1000/1000 ms. Memory limit 65000/65000/65000/65000 Kb.
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
Для отправки решений необходимо выполнить вход.
|