În tabără, copiii au inventat jocul Jump, care se joacă astfel: pe toată lungimea terenului de sport au desenat, în linie dreaptă, unul după altul, n+1 pătrăţele de laturi egale, numerotate distinct de la 0 la n. Orice jucător începe jocul de la linia de start, situată pe pătrăţelul numerotat cu 0 şi poate face un salt de pe poziţia pe care se află pe oricare dintre următoarele trei pătrăţele consecutive.
La un joc, fiecare participant trebuie să ajungă sărind de pe pătrăţelul de start până pe ultimul pătrăţel dar printr-o altă combinaţie de salturi decât a celorlalţi jucători anteriori.
Cerinţă
Ştiind că au fost desenate n+1 pătrăţele, să se determine numărul maxim de copii care pot juca Jump pe această configuraţie. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 666013.
Date de intrare
Fişierul de intrare jump.in conţine pe prima linie un număr natural n.
Date de ieşire
Fişierul de ieşire jump.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de copii, calculat modulo 666013, care pot participa la acest joc.
Restricţii
• 1 <= n <= 1000
Exemple
jump.in
jump.out
Explicaţii
4
7
Maxim 7 copii pot juca Jump.
O soluţie posibilă exprimată prin număr de pătrăţele sărite de fiecare jucător de la pătrăţelul de start la cel de oprire:
Jucătorul 1: 1 2 1
Jucătorul 2: 1 1 2
Jucătorul 3: 2 1 1
Jucătorul 4: 1 3
Jucătorul 5: 3 1
Jucătorul 6: 2 2
Jucătorul 7: 1 1 1 1