Fibonaççi ardıcıllığının ilk hədləri belədir:

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

Bu ardıcıllıqda ilk iki ədədin 1 və digərlərinin özündən əvvəlki iki həddin cəminə bərabər olmasını görmək çətin deyil.

Başqa sözlərlə, Fibonaççi ədədləri verilmiş rekurrent düstür ilə hesablanır

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

n-ci Fibonaççi ədədini tapan proqram yazın.

Giriş verilənləri

n (1 ≤ n ≤ 10000) natural ədədi.

Çıxış verilənləri

Çıxışa n-ci Fibonaççi ədədini verin.