În parcul orașului există trei rânduri de câte n copaci perfect aliniați. Rândurile sunt notate A, B, C, iar copacii de pe fiecare rând sunt numerotați de la 1 la n, ca în imaginea de mai jos:

O veveriță jucăușă sare prin copaci astfel:

• pornește dintr-un copac numerotat cu 1;
• la fiecare pas sare dintr-un copac numerotat cu i într-un copac numerotat cu i+1. Dacă se află într-un copac de pe rândul A sau de pe rândul C, va sări în copacul de pe rândul B, iar dacă se află în copacul de pe răndul B, va sări în copacul de pe rândul A sau în copacul de pe rândul C;
• se oprește într-unul dintre copacii numerotați cu n.

Cerința

Aflați numărul M de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă n este mai mic sau egal cu 1000, atunci veți afișa chiar numărul M, iar dacă n este mai mare decât 1000, veți afișa restul împărțirii lui M la 666013.

Date de intrare

Fișierul de intrare veverita.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire veverita.out va conține pe prima linie valoarea cerută.

Restricții și precizări

• 1 ≤ n ≤ 1018
• pentru 30% din teste, n ≤ 100;
• pentru alte 30% din teste, n ≤ 103;
• pentru alte 20% din teste, n ≤ 105;

Exemplul 1

veverita.in

3

veverita.out

6

Explicație

Exemplul 2

veverita.in

100000

veverita.out

50827