Последовательность Фибоначчи

Последовательность Фибоначчи выглядит следующим образом:

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-ое число Фибоначчи.

Примеры