Задачі
Фібоначчі
Фібоначчі
Числа Фібоначчі --- це послідовність чисел $f(n)$, яка задається формулою:
\begin{itemize}
\item $f(0) = 1$,
\item $f(1) = 1$,
\item $f(n) = f(n - 1) + f(n - 2)$
\end{itemize}
За заданим числом $n$ виведіть $n$-те число Фібоначчі.
\InputFile
Невід'ємне число $n~(n \le 45)$ --- номер числа Фібоначчі, яке потрібно вивести.
\OutputFile
Виведіть $n$-те число Фібоначчі.
Вхідні дані #1
4
Вихідні дані #1
5