Fibonacci Sequence#771

Fibonacci Sequence

1 second

128 megabytes

Medium

Fibonacci sequence is as follows:

$1$ , $1$ , $2$ , $3$ , $5$ , $8$ , $13$ , $21$ , $\dots$

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, are equal to the sum of the two previous numbers.

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

f_{1} = 1, f_{2} = 1, f_{n} = f_{n - 1} + f_{n - 2}

f_1 = 1, \quad f_2 = 1, \quad f_n = f_{n-1} + f_{n-2}

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

Input

One positive integer $n$ ( $1 \leq n \leq 10000$ 1 \leq n \leq 10000).

Output

Print the $n$ -th Fibonacci number.

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

f_{1} = 1, f_{2} = 1, f_{n} = f_{n - 1} + f_{n - 2}

1 \leq n \leq 10000