echival2

Cerință

Fie mulţimea $M= \{1, 2, 3, \dots , 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:

1. să schimbăm două elemente de pe o aceeaşi coloană (figura $1 \rightarrow$ figura $2$)
2. să schimbăm două coloane între ele (figura $1 \rightarrow$ figura $3$)
3. să schimbăm în bipermutare două valori distincte $x$ şi $y$ între ele (figura $1 \rightarrow$ figura $4$)

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ţă.

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• $3 \leq n \leq 100 \ 000$;
• Problema valora $50$ de puncte în concurs

Exemplu

echival2.in

5

echival2.out

2

Explicație

Mulţimea bipermutărilor de ordin $5$ se descompune în două clase de echivalenţă.