Последовательность Фибоначчи выглядит следующим образом:
1, 1, 2, 3, 5, 8, 13, 21, ….
Не трудно видеть, что в этой последовательности первые два числа равны 1, а все остальные числа, начиная с третьего, равны сумме двух предыдущих.
Другими словами, последовательность Фибоначчи задается следующим рекуррентной формулой:
f[1]
= 1, f[2]
= 1, f[n]
= f[n-1]
+ f[n-2]
Напишите программу, которая находит n-ое число Фибоначчи.
Одно натуральное число n (1 ≤ n ≤ 10000).
Вывести n-ое число Фибоначчи.