Cerința

Șirul lui Fibonacci este definit astfel:

$$F_n=\{\begin{array}{ll}1& \text{dacă }n=1\text{ sau }n=2,\\ F_{n-1}+F_{n-2}& \text{dacă }n>2.\end{array}$$

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 ...