e-olymp
Problems

Fibonacci

Fibonacci

Fibonacci numbers is a sequence of numbers F(n), given by the formula:

F(0) = 1, F(1) = 1, F(n) = F(n - 1) + F(n - 2)

Given the value of n. Print the n-th Fibonacci number.

Input

Nonnegative integer n (n45) - the Fibonacci number that must be printed.

Output

Print the n-th Fibonacci number.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
Output example #1
5