== 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 inmultirea polinoamelor in timp liniar, de rezolvarea conjecturilor sau a altor banalitati precum “Traveling salesman problem”, Nry s-a decis sa porneasca in cautarea secretului fericirii eterne. Privind insa in jurul sau, a constatat cu stupoare ca olimpicii recurg la tehnici necurate in acest joc pentru satisfactie, de la sustrasul subtil al surselor sau al ideilor de probleme, pana la acte mult mai grave, precum insusirea locurilor la IOI sau a editiilor precedente de Junior Challenge. Dorind insa sa fie original (si sa pastreze in acelasi timp noua traditie), Nry a ajuns la urmatoarea concluzie: trebuie sa subtilizeze Matrita!

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$).

Odata ajuns in posesia elixirului magic, acesta l-a asezat intr-un colt al Beciului Olimpic (unul din cele mai sigure adaposturi, in care dusmanii pot patrunde doar prin tavanul de sticla). Insa, pentru a se asigura ca noua sa achizitie nu va disparea in mod neasteptat, acesta a decis sa formeze un sistem de aparare in modul urmator: el a privit Beciul ca o matrice patratica de latura $N + 1$ (liniile si coloanele sunt numerotate de la 0 la N), Matrita aflandu-se in patratul aflat pe linia 0 si coloana 0. El doreste sa plaseze mai multe capcane in patrate cu indicii liniilor si ai coloanelor cuprinsi intre $1$ si $N$, astfel incat fiecare capcana sa fie vizibila din punctul in care se afla Matrita (cu alte cuvinte, sa nu existe doua capcane situate in $(l1, c1)$, respectiv $(l2, c2)$ si un numar real $k$ cu proprietatea ca $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 va roaga sa raspundeti la urmatoarea intrebare: stiind numarul $N$, in cate moduri isi poate construi el sistemul de aparare al Matritei? Raspunsul trebuie afisat **modulo $MOD$** (un numar *prim* citit din fisierul de intrare).

h2. Date de intrare

Fişierul de intrare $matrita.in$ conţine o singura linie pe care sunt scrise doua numere, $N$ şi $MOD$, cu semnificaţia din enunţ.

Fişierul de intrare $matrita.in$ contine o singura linie pe care sunt scrise doua numere, $N$ si $MOD$, cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $matrita.out$ veţi afişa un singur număr natural, şi anume răspunsul cerinţei **modulo $MOD$**.

În fişierul de ieşire $matrita.out$ veti afisa un singur numar natural, si anume raspunsul cerintei **modulo $MOD$**.

h2. Restricţii

* Nry dispune de un număr nelimitat de capcane
* Fiind foarte paranoic, acesta va plasa întotdeauna cel putin o capcana

* Nry dispune de un numar nelimitat de capcane
* Fiind foarte paranoic, acesta va plasa intotdeauna cel putin o capcana

* $1 ≤ N ≤ 12.000.000$

* $100.000.000 ≤ MOD ≤ 1.000.010.000$, $MOD$ e număr *prim*
* $Subtask 1 - 5 puncte N ≤ 10 şi MOD = 1000000007$
* $Subtask 2 - 10 puncte N ≤ 1900 si MOD = 1000000007$
* $Subtask 3 - 15 de puncte N ≤ 4250 şi MOD = 1000000007$
* $Subtask 4 - 30 de puncte N ≤ 750.000$
* $Subtask 5 - 30 de puncte N ≤ 5.000.000$
* $Subtask 6 - 10 puncte N ≤ 12.000.000$
* Legenda spune ca oricine gusta din Matriţă are un loc asigurat la $IOI 2020$

* $100.000.000 ≤ MOD ≤ 1.000.010.000$, $MOD$ e numar *prim*
* Subtask 1: Pentru teste in valoare 5 puncte $N ≤ 10$ si $MOD = 1000000007$
* Subtask 2: Pentru alte teste in valoare de 10 puncte $N ≤ 1900$ si $MOD = 1000000007$
* Subtask 3: Pentru alte teste in valoare de 15 de puncte $N ≤ 4250$ si $MOD = 1000000007$
* Subtask 4: Pentru alte teste in valoare de 30 de puncte $N ≤ 750.000$
* Subtask 5: Pentru alte teste in valoare de 30 de puncte $N ≤ 5.000.000$
* Subtask 6: Pentru alte teste in valoare de 10 puncte $N ≤ 12.000.000$
* Legenda spune ca oricine gusta din Matrita are un loc asigurat la IOI 2020

h2. Exemplu