Rabbits

Time Limit: 1 sec

 

The Problem

Suppose a newly-born pair of rabbits, one male, one female, are put in a field. Rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits. Suppose that our rabbits never die and that the female always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was...

# At the end of the first month, they mate, but there is still one only 1 pair.

# At the end of the second month the female produces a new pair, so now there are 2 pairs of rabbits in the field.

# At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field.

# At the end of the fourth month, the original female has produced yet another new pair, the female born two months ago produces her first pair also, making 5 pairs.

 

 

How many pairs will there be after N month?

 

The Input

Input file contains a series of line. Each line contains one integer numbers N (0< N <= 90) which is the month. Input is terminated by EOF.

 

The Output

For each case, how many rabbits pairs will be after N months.

 

Sample Input

1

3

4

 

Sample Output

1

3

5

 

 

 

 

Problem Setter: Shahin ShamS