Competitions

# 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 value of n. Find the n-th Fibonacci number.

#### Input

One 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