Bordura

bordura

== include(page="template/taskheader" task_id="bordura") ==

Primarul Bucurestiului s-a hotarat dintro-data sa construiasca foarte multe sensuri giratorii. Si pentru fiecare trebuie sa construiasca borduri (nu poti sa ai sensuri giratorii fara borduri). Spatiul din jurul sensului giratoriu e impartit in N sectoare numerotate de la 1 la N, oricare 2 sectoare consecutive fiind vecine. Pe deasupra sectorul 1 si sectorul N sunt si ele vecine. El are doua tipuri blocuri cu care poate sa bordeze sensurile giratorii, cele albastre (care ocupa 2 sectoare vecine pe un singur bloc) si cele rosii (care ocupa un singur sector).
 
Primarul Bucurestiului fiind un om artistic vrea ca toate sensurile giratorii sa fie bordate diferite, asa ca va roaga pe voi sa-i calculati cate bordari diferite exista pentru un sens giratoriu cu bordura impartita in N sectoare exista. Deoarece acest numar poate fi foarte mare el va roaga sa il afisati modulo *666013*.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $bordura.in$ va contine pe primul si singurul rand un numar natural N.

Fişierul de intrare $bordura.in$ ...

h2. Date de ieşire

În fişierul de ieşire $bordura.out$ trebuie sa se afle un singur numar reprezentand raspunsul la intrebarea primarului.

În fişierul de ieşire $bordura.out$ ...

h2. Restricţii

* $3 ≤ N ≤ 100.000$
* $Pentru teste valorand 20% din punctajul maxim N ≤ 15$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. bordura.in |_. bordura.out |

| 3
| 4

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Cele 4 bordari diferite sunt:
RRR
AAR
ARA
RAA
 
unde cu A am notat un sector peste care s-a pus un bloc albastru, iar cu R un sector peste care s-a pus un bloc rosu.
 
De observat ca RRA nu e solutie pentru ca blocurile albatre acopera 2 sectoare vecine, nu pot ocupa un singur sector.
 

...

== include(page="template/taskfooter" task_id="bordura") ==