Фибоначчи

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

• $f(0)=1$,

• $f(1)=1$,

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

По заданному числу $n$ выведите $n$-ое число Фибоначчи.

Входные данные

Неотрицательное число $n(n\le 45)$ — номер числа Фибоначчи, которое следует вывести.

Выходные данные

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

Примеры