Problems

# 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