Фібоначчі

Числа Фібоначчі — це послідовність чисел $f(n)$, яка задається формулою:

• $f(0)=1$,

• $f(1)=1$,

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

За заданим числом $n$ виведіть $n$-те число Фібоначчі.

Вхідні дані

Невід'ємне число $n(n\le 45)$ — номер числа Фібоначчі, яке потрібно вивести.

Вихідні дані

Виведіть $n$-те число Фібоначчі.

Приклади