sortari2

Sortari2

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

Poveste şi cerinţă...

Micul Johny se relaxează sortând permutări. Astfel, el alege la întâmplare o permutare cu $N$ elemente. Cât timp această permutare nu e sortată crescător, Johny alege două numere de pe poziţii consecutive în permutare şi le interschimbă. După un timp învaţă cum să sorteze orice permutare prin procedeul de mai sus cu număr minim de interschimbări.
După ce Johny îşi îmbunătăţeşte deprinderile algoritmice, în loc să interschimbe doar elemente de pe poziţii consecutive, el va putea interschimba oricare două elemente din permutare. Johny învaţă să sorteze permutările folosind un număr minim de astfel de operaţii.
Evident, pentru orice permutare numărul minim de operaţii prin care se realizează sortarea folosind al doilea procedeu e mai mic sau egal decât numarul minim de operaţii folosind primul procedeu.
Determinaţi câte permutări cu $N$ elemente pot fi sortate mai rapid prin procedeul al doilea decât prin primul procedeu (cu număr optim de interschimbari mai mic). Deoarece răspunsul poate fi foarte mare, se va afişa doar restul împărţirii acestuia la $999017$.

h2. Date de intrare

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

Fişierul de intrare $sortari2.in$ conţine pe prima linie numărul natural $N$, cu semnificaţia din enunţ.

h2. Date de ieşire

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

Fişierul de ieşire $sortari2.out$ va conţine o singură linie pe care se va afla restul împărţirii răspunsului la $999017$.

h2. Restricţii

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

* $2 ≤ N ≤ 1000$

h2. Exemplu

table(example). |_. sortari2.in |_. sortari2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. sortari2.in |_. sortari2.out|
|4|11|

h3. Explicaţie

...

Sunt $11$ permutări cu proprietatea cerută:
$1 4 3 2$
$2 4 3 1$
$3 2 1 4$
$3 2 4 1$
$3 4 1 2$
$3 4 2 1$
$4 1 3 2$
$4 2 1 3$
$4 2 3 1$
$4 3 1 2$
$4 3 2 1$
De exemplu, permutarea $4 2 1 3$ poate fi sortată cu numar minim de paşi folosind primul procedeu astfel: $**4 2** 1 3$ => $2 **4 1** 3$ => $**2 1** 4 3$ => $1 2 **4 3**$ => $1 2 3 4$. Au fost necesari $4$ paşi. Folosind al doilea procedeu, permutarea poate fi sortată mai rapid astfel: $4 2 **1 3**$ => $**4** 2 3 **1**$ => $1 2 3 4$. Au fost necesari doar $2$ paşi.

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

5348