Echival2

echival2

== 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ă elemente de pe o aceeaşi coloană (figura 1 => figura 2)
* 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 un număr natural $n$, determinaţi numărul claselor de echivalenţă distincte modulo $1114111$.

Poveste şi cerinţă...

h2. Date de intrare

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

Fişierul de intrare $echival2.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $echival2.out$ ...

h2. Restricţii

* $2 < n &le; 100000$

* $... ≤ ... ≤ ...$

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

| 5
| 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

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

9051