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ța
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 de intrare sortari.in
conține o singură linie pe care se află numărul N
.
Date de ieșire
Fișierul de ieșire 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 și precizări
1 ≤ N ≤ 200
Exemplu:
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: 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)