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 (n ≤ 45) - the Fibonacci number that must be printed.

Output

Print the n-th Fibonacci number.