petrecere

Petrecere

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

Poveste şi cerinţă...

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:
$1.$ băiatul $i$ dansează cu fata $i$;
$2.$ băiatul $i$ dansează cu fata $j$ şi atunci obligatoriu băiatul $j$ dansează cu fata $i$.
De exemplu, 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)$
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.
 
h2. Cerintă
 
Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.

h2. Date de intrare

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

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

h2. Date de ieşire

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

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.

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 |

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

| 2
| 2

|

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") ==