Fibonacci

Fibonacci numbers is a sequence of numbers $f(n)$, defined by the formula:

• $f(0)=1$,

• $f(1)=1$,

• $f(n)=f(n-1)+f(n-2)$

Given a value of $n$, find the $n$-th Fibonacci number.

Input

One nonnegative integer $n(n\le 45)$, representing the Fibonacci number to be printed.

Output

Print the $n$-th Fibonacci number.

Examples