eolymp
bolt
Try our new interface for solving problems
Problems

Fibonacci

Fibonacci

Time limit 1 second
Memory limit 128 MiB

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