Toată lumea cunoaște modelul de deblocare a telefoanelor sub formă de o matrice cu 3 linii și 3 coloane. El are forma din figura de mai jos. Se pot trasa diferite modele de deblocare având un număr N de puncte prin care trecem, din fiecare punct putând merge la oricare vecin al lui. (Sunt maximum 8 vecini de exemplu pentru punctul din mijloc și 3 vecini pentru un punct din colț).

Determinați câte variante de modele sunt posibile trecând prin N puncte. Deoarece numărul poate fi foarte mare, se va afișa numărul de variante modulo 1000003.

Cerința

Să se scrie un program care citește N, lungimea modelului și afișează numărul de variante de realizare a modelului, modulo 1000003.

Date de intrare

Fișierul de intrare protection.in conţine pe primul rând numărul N reprezentând lungimea modelului.

Date de ieșire

Fișierul de ieșire protection.out va conține numărul de modele de terminat, modulo 1000003.

Restricții și precizări

• 1 ≤ N ≤ 2 000 000 000
• pentru 15% din teste, N ≤ 15
• pentru 35% din teste, N ≤ 200000
• pentru 50% din teste, N ≤ 2000000000
• Nu se trece de doua ori la rând prin același punct

Exemplul 1:

protection.in

3

protection.out

200

Exemplul 2:

protection.in

2

protection.out

40