Se consideră o matrice pătratică cu linii şi coloane ce conţine toate numerele naturale de la la .
Asupra matricei se definesc trei tipuri de operaţii codificate astfel:
- - interschimbarea coloanelor şi ale matricei
- - interschimbarea liniilor şi ale matricei
- - interschimbarea elementului de pe linia şi coloana cu elementul de pe linia şi coloana
Asupra matricei se efectuează un set de astfel de operaţii.
Cerință
Se cere să se determine numărul minim de aplicări complete ale acestui set de operaţii după care se ajunge din nou în starea iniţială. În cadrul setului operaţiile se efectuează mereu în aceeaşi ordine şi nu se poate sări peste o operaţie. Deoarece numărul acesta poate fi foarte mare se cere restul împărţirii sale la .
Date de intrare
Fişierul perspic.in
conţine pe prima linie numerele naturale şi , separate printr-un spaţiu, reprezentând dimensiunea matricei şi respectiv numărul de operaţii dintr-un set.
Pe următoarele linii se descriu operaţiile setului.
Date de ieșire
Fişierul perspic.out
va conţine restul împărţirii la al numărului minim determinat.
Restricții și precizări
- Pentru din teste numărul minim de aplicări ale setului de operaţii necesare va fi mai mic ca
Exemplul 1
perspic.in
2 2
C 1 2
R 1 2
perspic.out
2
Explicație
Matricea iniţială:
Matricea după prima operaţie:
Matricea după a doua operaţie(terminarea primului set):
Matricea după a treia operaţie:
Matricea după a patra operaţie(terminarea celui de al doilea set):
Exemplul 2
perspic.in
3 3
E 1 1 2 2
R 1 2
C 2 3
perspic.out
4