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

Послідовність Фібоначчі виглядає наступним чином:

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

Приклади