Fibonaccijev niz je niz prirodnih brojeva. Ako \(N-ti\) po redu broj označimo sa \(f(n)\), tada za ovaj niz vrijedi da je \(f(n) = f(n - 1) + f(n - 2)\). Također vrijedi i da je \(f(0) = 0\) te \(f(1) = 1\). Poznavajući ove informacije, moguće je izračunati sve ostale elemente ovoga niza.

Vaš je zadatak napisati funkciju koja će kao argument dobiti prirodni broj \(N\) te će kao povratnu vrijednost vratiti vrijednost \(N-tog\) po redu fibonaccijevog broja. Kako biste testirali funkciju, napišite i ostatak programa (funkcija main) u kojoj će se učitati prirodni broj \(N\), a nakon toga ispisati vrijednost koju vrati funkcija.

Bonus

Dodatno možete pokušati napraviti rekurzivnu funkciju. Više o rekurzijama možete naći na: https://en.wikipedia.org/wiki/Recursion_(computer_science)

Ulazni podaci

U jedinom retku ulaza, nalazi se prirodni broj \(N\).

Izlazni podaci

Potrebno je ispisati vrijednost \(N-tog\) po redu fibonaccijevog broja.

Primjeri test podataka

Ulaz

1

Izlaz

1

Ulaz

5

Izlaz

5