Fibonacci sequence is as follows:

1, 1, 2, 3, 5, 8, 13, 21, ….

It is not difficult to see that in this sequence, the first two numbers are equal to 1 and all other numbers, starting with the third, equal to the sum of the two previous.

In other words, the Fibonacci sequence given by the following recurrent formula:

f1 = 1, f2 = 1, fn = fn-1 + fn-2

Write a program that finds the n-th Fibonacci number.

Input

One positive integer n (1 ≤ n ≤ 10000).

Output

Print the n-th Fibonacci number.