eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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 (1n10000).

Вихідні дані

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

Приклад

Вхідні дані #1
1
Вихідні дані #1
1
Вхідні дані #2
3
Вихідні дані #2
2
Вхідні дані #3
5
Вихідні дані #3
5
Джерело Крим 2010