jump

Î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 $2010$.

Date de intrare

Fişierul de intrare jump.in conţine pe prima linie un număr natural $n$ ce reprezintă numărul de pătrăţele din joc.

Date de ieşire

Fişierul de ieşire jump.out va conţine un singur număr reprezentând numărul maxim de copii, calculat modulo $2010$, care pot participa la acest joc.

Restricţii

• $1 \leq n \leq 1\ 000$
• Definim $x$ modulo $2010$ ca fiind restul împărţirii întregi a lui $x$ la $2010$.
  • De exemplu, $2012$ modulo $2010$ este $2$.
• Proprietăţi:
  • $(a + b) \mod 2010 = ((a \mod 2010) + (b \mod 2010)) \mod 2010$
  • $(a \cdot b) \mod 2010 = ((a \mod 2010) \cdot (b \mod 2010)) \mod 2010$

Exemplu

jump.in

4

jump.out

7

Explicație

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$