== include(page="template/taskheader" task_id="sortari2") ==
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.

Totuşi, dupa un timp, Johny se maturizează şi îşi îmbunătăţeşte deprinderile algoritmice. Astfel, în loc să interschimbe doar elemente de pe poziţii consecutive, el poate interschimba acum oricare două elemente din permutare. Johny învaţă să sorteze permutările folosind un număr minim de operaţii de acest tip.

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$.

$4 2 3 1$
$4 3 1 2$
$4 3 2 1$

De exemplu, permutarea $3 2 1 4$ 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 sortata mai rapid astfel: $4 2 **1 3**$ => $**4** 2 3 **1**$ => $1 2 3 4$. Au fost necesari doar $2$ paşi.

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