Candale Silviu (silviu) Cerința
Șirul lui Fibonacci este definit astfel:
$$ F_n = \begin{cases}
1& \text{dacă } n = 1 \text{ sau } n = 2 ,\\
F_{n-1} + F_{n-2} & \text{dacă } n > 2.
\end{cases} $$
Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.
Date de intrare
Programul citește de la tastatură numărul n.
Date de ieșire
Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013.
Restricții și precizări
1 ≤ n ≤ 2.000.000.000
Exemplu:
Intrare
6
Ieșire
8
Explicație
Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...