Числа Фибоначчи определяются рекуррентной формулой:
\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \ при\ n > 2\)
Входные данные
В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).
Выходные данные
Вывести одно n-е число Фибоначчи - Fn.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 |
1 |
| 2 |
7 |
21 |