Liczby Fibonacciego

Leonardo z Pizy (ok. 1200 r.) zastanawiał się, ile par królików pojawiłoby się w n-tej generacji, gdyby zacząć proces rozmnażania od jednej pary i założyć, że każda para królików z k-tego pokolenia płodzi jedną parę należącą do następnego, (k+1)-wszego pokolenia i jedną z kolejnego, (k+2)-giego pokolenia, po czym umiera. Jeżeli w n-tym pokoleniu jest Fn par, to:

Ojciec Leonarda nosił przydomek Bonacci, stąd syn został Fibonaccim (filius Bonacci="syn dobrotliwego").

Napisz program, który policzy dla Fibonacciego wartość Fn.

Zadanie

Napisz program, który:

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita n (1<=n<=1000).

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać n-tą liczbę Fibonacciego. F1000 <10250.

Przykład

Dla danych wejściowych:

5

Poprawnym wynikiem jest:

5

Wskazówka: niewykluczone, że Leonardo Fibonacci już nie żyje. Tak czy siak, program napisać polecamy.