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