Petrecere

petrecere

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

Se organizează o petrecere la care participă $N$ băieţi (numerotaţi de la $1$ la $N$) şi $N$ fete (numerotate de la $1$ la $N$). S-a decis ca petrecerea să dureze mai multe minute. În fiecare minut fetele şi băieţii formează o configuraţie de dans, adică $N$ perechi, după una din următoarele reguli:
 
* băiatul $i$ dansează cu fata $i$;
* băiatul $i$ dansează cu fata $j$ şi atunci obligatoriu băiatul $j$ dansează cu fata $i$.
 
Prin perechea $(i, j)$ s-a notat faptul că băiatul $i$ dansează cu fata $j$. Două configuraţii sunt distincte dacă ele diferă prin cel puţin o pereche. Pentru $N = 7$, două configuraţii de dans posibile sunt:
$(1, 1) (2, 2) (3, 7) (4, 5) (5, 4) (6, 6) (7, 3)$
$(1, 1) (2, 2) (3, 3) (4, 5) (5, 4) (6, 6) (7, 7)$
 
h2. Cerinţă
 
Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $petrecere.in$ conţine pe prima linie un singur număr natural $N$.

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

h2. Date de ieşire

Fişierul de ieşire $petrecere.out$ va conţine o singură linie pe care va fi scris un singur număr natural reprezentând durata în minute a petrecerii.

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

h2. Restricţii

* $1 ≤ N ≤ 2000$
* Răspunsul este un număr natural de maximum $3000$ de cifre.
* Pentru $20%$ din teste, vom avea $N ≤ 11$.
* Pentru alte $20%$ din teste, rezultatul poate fi reprezentat pe $64$ de biţi cu semn.

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

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

| 2
| 2

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

|

table(example).
| 3
| 4
|

h3. Explicaţie

Pentru primul exemplu, configuraţiile de dans sunt:
$(1, 1) (2, 2)$
$(1, 2) (2, 1)$
 
Pentru al doilea exemplu, configuraţiile de dans sunt:
$(1, 1) (2, 2) (3, 3)$
$(1, 1) (2, 3) (3, 2)$
$(1, 2) (2, 1) (3, 3)$
$(1, 3) (2, 2) (3, 1)$

...

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

4752