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.
Napisz program, który:
W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita n (1<=n<=1000000000).
W pierwszym i jedynym wierszu wyjścia należy wypisać n-tą liczbę Fibonacciego. Ponieważ wynik może być raczej duży, a tak duże liczby raczej nie interesują Leonarda Fibonacciego, to należy wypisać wynik modulo 123456789 (czli resztę z dzielenia wyniku przez 123456789).
Dla danych wejściowych:
5
Poprawnym wynikiem jest:
5
Wskazówka: niewykluczone, że Leonardo Fibonacci już nie żyje. Tak czy siak, i ten program napisać polecamy.
[Zgłoś rozwiązanie] [Moje zgłoszenia]