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 value of n. Find the n-th Fibonacci number.
Input data
One nonnegative integer n~(n \le 45) — the Fibonacci number that must be printed.
Output data
Print the n-th Fibonacci number.
Examples
Input example #1
4
Output example #1
5