sortari

Balaurului Arhirel nu îi plac prea mult şirurile care nu sunt ordonate. Din acest motiv, nu poate să suporte permutările de $N$ elemente, aşa că se decide să le sorteze şi pentru asta inventează o metodă proprie de sortare.

El ia iniţial un şir $S$ care reprezintă o permutare de ordin $N$. Caută în şirul $S$ cel mai mic ($min$) şi cel mai mare element ($max$). Să considerăm că $min$ se află în şirul $S$ pe poziţia $p_{min}$, iar $max$ pe poziţia $p_{max}$. Să notăm cu $x$ minimul dintre $p_{min}$ şi $p_{max}$, iar cu $y$ maximul dintre $p_{min}$ şi $p_{max}$. Şirul $S$ a fost astfel partiţionat în alte trei şiruri, $S_1$, $S_2$, $S_3$ care pot avea fiecare zero elemente, un element sau mai multe elemente. Şirul $S_1$ începe la prima poziţie din şir şi se termină la poziţia $x-1$. Şirul $S_2$ începe la poziţia $x+1$ şi se termină la poziţia $y-1$. Şirul $S_3$ începe la poziţia $y+1$ şi se termină la ultima poziţie din şir.

Balaurul Arhirel mută valoarea min la capătul din stânga al lui $S$, iar valoarea $max$ la capătul din dreapta al şirului $S$ şi reia sortarea pentru fiecare din şirurile $S_1$, $S_2$, $S_3$.

De exemplu să considerăm $N = 6$ şi şirul $S$ = ($3 \ 4 \ 2 \ 1 \ 6 \ 5$). La primul pas, $min = 1$ şi $max = 6$. Deci $S_1$ = ($3 \ 4 \ 2$); $S_2$ = (); $S_3$ = ($5$). Se mută $min$ şi $max$ la capetele şirului şi se obţine $S$ = ($1 \ 3 \ 4 \ 2 \ 5 \ 6$) şi se sortează în acelaşi mod $S_1$, $S_2$ şi $S_3$. $S_2$ şi $S_3$ au $0$, respectiv $1$ element, deci sunt deja sortate. Pentru $S_1$, se găseşte $min = 2$ şi $max = 4$ şi vom avea şirurile ($3$); (); (). Se mută $min$ şi $max$ la capete şi se obţine $S_1$ = ($2 \ 3 \ 4$). În final, vom avea şirul $S$ = ($1 \ 2 \ 3 \ 4 \ 5 \ 6$). Evident, această metodă nu va funcţiona întotdeauna pentru sortarea unei permutări.

Spre exemplu, pentru şirul $S$ = ($3 \ 4 \ 1 \ 6 \ 5 \ 2$), se găseşte $min = 1$ şi $max = 6$, iar $S_1$ = ($3 \ 4)$, $S_2$ = (), $S_3$ = ($5 \ 2$). Se mută $min$ şi $max$ la capetele lui $S$ : $S$ = ($1 \ 3 \ 4 \ 5 \ 2 \ 6$) şi se procedează la sortarea pe rând a şirurilor $S_1$, $S_2$, $S_3$. $S_1$ este sortat, $S_2$ nu are elemente, iar $S_3$ va deveni $S_3$ = ($2 \ 5$). În final, $S$ = ($1 \ 3 \ 4 \ 2 \ 5 \ 6$).

Cerinţă

Ajutaţi-l pe Balaurul Arhirel să afle câte dintre permutările de $N$ elemente pot fi sortate prin metoda sa.

Date de intrare

Fişierul sortari.in conţine o singură linie pe care se află numărul $N$.

Date de ieşire

Fişierul sortari.out va conţine o singură linie pe care se află numărul de permutări de ordin $N$ ce pot fi sortate prin metoda balaurului modulo $19 \ 573$ (restul împărţirii numărului de permutări la $19 \ 573$).

Restricții și precizări

• $0 < N < 201$;

Exemplul 1

sortari.in

4

sortari.out

18

Explicație

În cazul permutărilor de câte $4$ elemente, şirurile ($1 \ 3 \ 4 \ 2$); ($3 \ 1 \ 2 \ 4$); ($3 \ 1 \ 4 \ 2$); ($3 \ 4 \ 1 \ 2$); ($3 \ 4 \ 2 \ 1$); ($4 \ 3 \ 1 \ 2$) nu vor putea fi sortate crescător. Celelalte $24 - 6 = 18$ permutări pot fi sortate crescător.
De exemplu, pentru şirul ($1 \ 3 \ 4 \ 2$), după găsirea $min = 1$, $max = 4$, se obţin şirurile: $S_1 = ()$; $S_2 = (3)$; $S_3 = (2)$, care, având câte un element sunt sortate. Astfel, după mutarea la capete a lui $min$ şi $max$ vom avea: ($1 \ 3 \ 2 \ 4$)