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

Un turist roman a plecat intr-o excursie pe Marea Mediterana. El a ajuns intr-unul dintre orasele de pe una din cele $3$ insule pe care doreste sa le viziteze. Fiecare insula are exact $N$ orase si toate sunt porturi. Turistul doreste sa isi inceapa calatoria din orasul in care se afla, sa viziteze toate celelalte $3*N-1$ orase exact o data si apoi sa se intoarca in orasul de unde si-a inceput calatoria, pentru a pleca apoi inapoi spre casa.

Un turist roman a plecat intr-o excursie pe Marea Mediterana. El a ajuns intr-unul dintre orasele de pe una din cele $3$ insule pe care doreste sa le viziteze. Fiecare insula are exact $N$ orase si toate sunt porturi. Turistul doreste sa isi inceapa calatoria din orasul in care se afla, sa viziteze toate celelalte $3*N-1$ orase exact o data si apoi sa se intoarca in orasul de unde si-a inceput calatoria, pentru a pleca dupa aceea inapoi spre casa.

Din pacate, pe fiecare din cele $3$ insule traiesc triburi de canibali, astfel incat este interzis de catre autoritati sa se calatoreasca direct intre $2$ orase de pe aceeasi insula. Din fericire, exista rute maritime intre orice pereche de orase care nu se afla pe aceeasi insula. Nu exista rute maritime intre $2$ orase de pe aceeasi insula.

h2. Date de intrare

Fisierul d eintrare $rute.in$ contine un singur numar intreg $N$, reprezentand numarul de orase de pe fiecare din cele $3$ insule.

Fisierul de intrare $rute.in$ contine un singur numar intreg $N$, reprezentand numarul de orase de pe fiecare din cele $3$ insule.

h2. Date de iesire

In fisierul de iesire $rute.out$ veti afisa numarul de posibilitati de planificare a calatoriei. $2$ calatorii se considera identice daca secventa de $3*N$ orase vizitate este identica sau daca secventa oraselor vizitate in cadrul primei calatorii este identica cu secventa oraselor vizitate in a dou acalatorie, dar citita invers (de exemplu, daca fiecare insula ar avea un singur oras, numerotat cu numarul insulei, calatoriile $1-2-3-1$ si $1-3-2-1$ ar fi identice).

In fisierul de iesire $rute.out$ veti afisa numarul de posibilitati de planificare a calatoriei. $2$ calatorii se considera identice daca secventa de $3*N$ orase vizitate este identica sau daca secventa oraselor vizitate in cadrul primei calatorii este identica cu secventa oraselor vizitate in a doua calatorie, dar citita invers (de exemplu, daca fiecare insula ar avea un singur oras, numerotat cu numarul insulei, calatoriile $1-2-3-1$ si $1-3-2-1$ ar fi identice).

h2. Restrictii

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

2299