Şirul de numere Fibonacci este definit în felul următor: primele două elemente ale şirului sunt egale cu 1, fiecare element următor este suma celor două elemente care îl precedă.
Şirul de numere Fibonacci este scris fără spaţii, astfel încât începutul lui arată în felul următor:
11235813213455...

Cerinţă

Se cere să scrieţi un program care să determine cifra de pe poziţia N din şirul obţinut (poziţiile în şir sunt numerotate începând cu 1).

Date de intrare

Fişierul de intrare fib.in va conţine un singur număr N – poziţia cifrei.

Date de ieşire

Fişierul de ieşire fib.out va conţine o singură linie pe care va fi afişat un număr natural – valoarea cifrei de pe poziţia N.

Restricţii

• 1 ≤ N ≤ 10000000

Exemple

fib.in	fib.out	Explicaţii
6	8	112358
fib.in	fib.out	Explicaţii
14	5	11235813213455

prof. Sergiu Corlat

Liceul „Orizont” Chişinău

scorlat@gmail.com