Fișierul intrare/ieșire:	fibonacci.in, fibonacci.out	Sursă	Cerc informatică Vianu
Autor	din folclor	Adăugată de	Cristian Francu •francu
Timp execuție pe test	2.5 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1/5

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile trimise | Statistici

Fibonacci (clasa a 7-a)

Notă: acesta este un exercițiu introductiv în recursivitate. Pentru a avea sens respectați cerința întocmai, rezolvîndu-l cu o funcție recursivă. Dacă scrieți corect funcția ea nu trebuie să conțină instrucțiuni de ciclare, gen for, while sau do … while.

Se citește un număr n mai mic decît 100 000 000. Să se calculeze al n-lea termen al șirului lui Fibonacci, modulo 982451653 folosind o funcție recursivă la coadă. Funcția va fi apelată inițial astfel:

fib( n, 1, 1 );

sau, pentru optimizare:

fib( n, 0, 1 );

Șirul lui Fibonacci se consideră a fi:

1 1 2 3 5 8 13 21 …

Date de intrare

Fișierul de intrare fibonacci.in conține un singur număr n cu semnificația de mai sus.

Date de ieșire

În fișierul de ieșire fibonacci.out se va scrie un singur număr și anume cel de-al n-ulea termen al șirului lui Fibonacci modulo 982451653.

Restricții

• 1 ≤ n ≤ 100 000 000
• Implementarea trebuie să fie recursivă

Exemplu