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.
Cerința
Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.
Date de intrare
Fișierul de intrare petrecere.in
conține pe prima linie un singur număr natural N
.
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.
Restricții și precizări
1 ≤ N ≤ 2000
- Răspunsul este un număr natural de maximum
3000
de cifre. - Pentru
20%
din teste, vom aveaN ≤ 11
. - Pentru alte
20%
din teste, rezultatul poate fi reprezentat pe64
de biți cu semn.
Exemplul 1:
petrecere.in
2
petrecere.out
2
Explicație
Configuraţiile de dans sunt:
(1,1) (2,2)
(1,2) (2,1)
Exemplul 2:
petrecere.in
3
petrecere.out
4
Explicație
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)