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 kbytes
Scorul tău	N/A	Dificultate	1/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile 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