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

Plictisit de înmulţirea polinoamelor în timp liniar, de rezolvarea conjecturilor sau a altor banalităţi precum “Traveling salesman problem”, $Nry$ s-a decis sa pornească în căutarea secretului fericirii eterne. Privind însa în jurul său, a constatat cu stupoare că olimpicii recurg la tehnici necurate în acest joc pentru satisfacţie, de la sustrasul subtil al surselor sau al ideilor de probleme, pana la acte mult mai grave, precum însuşirea locurilor la $IOI$ sau a ediţiilor precedente de Junior Challenge. Dorind însa sa fie original (şi să păstreze în acelaşi timp noua tradiţie), $Nry$ a ajuns la următoarea concluzie: trebuie sa subtilizeze Matriţa!

Plictisit de înmulţirea polinoamelor în timp liniar, de rezolvarea conjecturilor sau a altor banalităţi precum “Traveling salesman problem”, $Nry$ s-a decis sa pornească în căutarea secretului fericirii eterne. Privind însa în jurul său, a constatat cu stupoare că olimpicii recurg la tehnici necurate în acest joc pentru satisfacţie, de la sustrasul subtil al surselor sau al ideilor de probleme, pana la acte mult mai grave, precum însuşirea locurilor la $IOI$ sau a ediţiilor precedente de Junior Challenge. Dorind însa sa fie original (şi să păstreze în acelaşi timp noua tradiţie), Nry a ajuns la următoarea concluzie: trebuie sa subtilizeze Matriţa!

Odată ajuns în posesia elixirului magic, acesta l-a aşezat într-un colt al Beciului Olimpic (unul din cele mai sigure adăposturi, în care duşmanii pot pătrunde doar prin tavanul de sticla). Însa, pentru a se asigura ca noua sa achiziţie nu va dispărea în mod neaşteptat, acesta a decis să formeze un sistem de apărare în modul următor: el a privit Beciul ca o matrice pătratica de latura $N + 1$ (liniile şi coloanele sunt numerotate de la $0$ la $N$), Matriţa aflându-se în pătratul aflat pe linia $0$ şi coloana $0$. El doreşte sa plaseze mai multe capcane în pătrate cu indicii liniilor şi al coloanelor cuprinşi intre $1$ şi $N$, astfel încât fiecare capcana să fie vizibilă din punctul în care se afla Matriţa (cu alte cuvinte, sa nu existe doua capcane situate în $(l1, c1)$, respectiv $(l2, c2)$ şi un număr real $k$ cu proprietatea că $x1 = x2 * k$ si $y1 = y2 * k$).

$Nry$ vă roagă sa răspundeţi la următoarea întrebare: ştiind numărul $N$, în câte moduri îşi poate construi el sistemul de apărare al Matriţei? Răspunsul trebuie afişat **modulo $MOD$** (un număr *prim* citit din fişierul de intrare).

Nry vă roagă sa răspundeţi la următoarea întrebare: ştiind numărul $N$, în câte moduri îşi poate construi el sistemul de apărare al Matriţei? Răspunsul trebuie afişat **modulo $MOD$** (un număr *prim* citit din fişierul de intrare).

h2. Date de intrare

h2. Restricţii

* $Nry$ dispune de un număr nelimitat de capcane

* Nry dispune de un număr nelimitat de capcane

* Fiind foarte paranoic, acesta va plasa întotdeauna cel putin o capcana
* $1 ≤ N ≤ 12.000.000$
* $100.000.000 ≤ MOD ≤ 1.000.020.000$, $MOD$ e număr *prim*