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 pmin, iar max pe poziţia pmax. Să notăm cu x minimul dintre pmin şi pmax, iar cu y maximul dintre pmin şi pmax. Şirul S a fost astfel partiţionat în alte trei şiruri, S1 S2 S3 care pot avea fiecare zero elemente, un element sau mai multe elemente. Şirul S1 începe la prima poziţie din şir şi se termină la poziţia x-1. Şirul S2 începe la poziţia x+1 şi se termină la poziţia y-1. Şirul S3 î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 S1, S2, S3.
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 S1=(3 4 2); S2=(); S3=(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 S1, S2 şi S3. S2 şi S3 au 0, respectiv 1 element, deci sunt deja sortate. Pentru S1, 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 S1=(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 S1=(3 4), S2=(), S3=(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 S1, S2, S3. S1 este sortat, S2 nu are elemente, iar S3 va deveni S3=(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 19573 (restul împărţirii numărului de permutări la 19573).
Restricţii
0<N<201
Exemple
sortari.in
sortari.out
Explicaţii
4
18
Î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: S1=(); S2=(3); S3=(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)