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:

`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.

Input example #1

1

Output example #1

1

Input example #2

3

Output example #2

2

Input example #3

5

Output example #3

5