== include(page="template/taskheader" task_id="echival1") ==

== include(page="template/taskheader" task_id="echival2") ==

Fie mulţimea $M = {1, 2, 3, ... , n}$. Vom defini o bipermutare de ordin $n$ ca o matrice $a$ cu două linii şi $n$ coloane, în care fiecare număr $k$ al mulţimii $M$ apare în matrice pe două coloane distincte (figurile 1, 2, 3 şi 4 conţin câte o bipermutare, iar matricea din figura 0 nu este bipermutare). Într-o bipermutare putem efectua următoarele operaţii:

* să schimbăm două coloane între ele (figura 1 => figura 3)
* să schimbăm în bipermutare două valori distincte $x$ şi $y$ între ele (figura 1 => figura 4)

!problema/echival2?image.jpg!
 

Două bipermutări sunt echivalente, dacă există o succesiune de operaţii prin care din prima bipermutare se poate ajunge la a doua bipermutare. În figurile de mai sus toate cele patru bipermutări sunt echivalente. Dacă două bipermutări sunt echivalente, atunci ele aparţin aceleiaşi clase de echivalenţă.
h2. Cerinţă

Dându-se o bipermutare de ordin $n$ verificaţi echivalenţa acesteia cu alte $10$ bipermutări de ordin $n$.

Dându-se un număr natural $n$, determinaţi numărul claselor de echivalenţă distincte modulo $1114111$.

h2. Date de intrare

Fişierul de intrare $echival1.in$ conţine pe prima linie numărul natural $n$, cu semnificaţia de mai sus. Următoarele $2$ linii conţin câte $n$ numere separate prin spaţiu şi descriu bipermutarea ce urmează a fi verificată, următoarele $20$ de linii descriu analog cele $10$ bipermutări ale setului, câte una pe două linii.

Fişierul de intrare $echival2.in$ conţine pe prima linie numărul natural $n$, cu semnificaţia de mai sus.

h2. Date de ieşire

Fişierul de ieşire $echival1.out$ va conţine pe $10$ linii consecutive, în ordinea bipermutărilor citite din fişierul de intrare, câte un număr natural astfel: $1$, dacă bipermutarea curentă este echivalentă cu prima bipermutare citită şi $0$, în caz contrar.

Fişierul de ieşire $echival2.out$ va conţine pe prima linie numărul claselor de echivalenţă modulo $1114111$.

h2. Restricţii

h2. Exemplu

table(example). |_. echival1.in |_. echival1.out |

table(example). |_. echival2.in |_. echival2.out |

| 5

5 3 4 1 2
2 4 1 3 5
5 2 4 4 1
3 1 5 3 2
1 1 2 3 4
2 4 5 5 3
1 1 5 3 4
4 3 2 2 5
2 1 3 4 4
1 5 2 3 5
3 2 4 1 1
5 3 2 4 5
3 4 5 5 1
4 2 3 1 2
1 3 2 3 4
4 1 5 5 2
5 2 5 1 1
3 4 2 4 3
4 4 5 2 1
1 2 3 3 5
3 5 3 2 2
1 1 5 4 4
| 1
0
0
0
0
0
0
0
0
1

| 2

|

== include(page="template/taskfooter" task_id="echival1") ==

== include(page="template/taskfooter" task_id="echival2") ==

9051