Fibonacci Sequence

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:

f[1] = 1, f[2] = 1, f[n] = f[n-1] + f[n-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.

Examples