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

1, 1, 2, 3, 5, 8, 13, 21, ….

Не трудно видеть, что в этой последовательности первые два числа равны 1, а все остальные числа, начиная с третьего, равны сумме двух предыдущих.

Другими словами, последовательность Фибоначчи задается следующим рекуррентной формулой:

f1 = 1, f2 = 1, fn = fn-1 + fn-2

Напишите программу, которая находит n-ое число Фибоначчи.

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

Одно натуральное число n (1 ≤ n ≤ 10000).

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

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