Inel

inel

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

!> problema/inel?inel.png 60%!
 
Un inel este compus din $N$ cercuri ca în desenul alăturat. Puneţi numerele naturale $1$, $2$, ..., $N$ în fiecare cerc separat, astfel încât suma numerelor din două cercuri adiacente de pe inel să fie un număr prim.
 
Atenţie! Pentru a nu număra de mai multe ori aceeaşi soluţie, considerăm că numărul $1$ este fixat într-un cerc de pe inel.
 
h2. Cerinţă
 
Scrieţi un program care calculează numărul de moduri în care numerele naturale $1$, $2$, ..., $N$  se pot pune în cercuri astfel încât să fie respectate condiţiile din enunţ.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie a fişierului de intrare $inel.in$ se află un număr natural $N$, având semnificaţia din enunţ.

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

h2. Date de ieşire

În fişierul de ieşire $inel.out$ se va afla un singur număr natural, reprezentând numărul cerut.

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

h2. Restricţii

* $2 ≤ N ≤ 18$

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

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

| 8
| 4

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

|
h3. Explicaţie

Cele $4$ moduri de a aranja numerele sunt:
$1 2 3 8 5 6 7 4$
$1 2 5 8 3 4 7 6$
$1 4 7 6 5 8 3 2$
$1 6 7 4 3 8 5 2$
 

...

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

5469