Description

Everyone has once heard about Fibonacci numbers, which have a lot of applications in mathematics and informatic sciences, and everyone knows the history about the mathematician (Fibonacci) who created the sequence, but no one until some years ago has heard about his spanish brother Fibonacho (yeah, Fibonacci was italian, but his father really enjoyed his life, besides in that time there wasn´t acm contest neither TV). Fibonacho also created a sequence, which doesn’t have any particular or important application, but it was necessary to increment Fibonachos’ ego who felt bad about his brother had a sequence and he didn’t. So Fibonacho created the next sequence:

1, 1, 1, 3, 5, 9, 17, 31, 57, ...

So Fibonacho(1) = 1,Fibonacho(2) = 1 and Fibonacho(9) = 57

Fibonacho wasn´t really a mathematician, so he didn´t write a formula to get Fibonacho’s numbers, but a monkey can see the sequence in his numbers.

Your problem here is to write a program than read a number n between 1 and 20 and print the Fibonacho(n) number, really easy does not it?, well it had to be a really easy problem for you to not feel so bad about not doing a single problem in this contest and kill your brother like Fibonacho, yeah Fibonacci didnt die for cancer, Fibonacho killed him.

Input

The input will consist of a number of test cases. Each one is a line containing n (1 ≤ n ≤ 20). Input is terminated by EOF.

Output

For each test case, output one line containing the corresponding fibonnacho(n).

1
6
9

1
9
57

Problemsetter: Hugo Sánchez Ricardez