Задачи
Фибоначчи
Фибоначчи
Числа Фибоначчи --- это последовательность чисел $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