eolymp
Problems

Fibonacci Sequence

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:

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

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

Input

One positive integer n (1n10000).

Output

Print the n-th Fibonacci number.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
Output example #1
1
Input example #2
3
Output example #2
2
Input example #3
5
Output example #3
5
Source Crimea 2010