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

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 citit din fisierul de intrare).

h2. Date de intrare

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

* $1 ≤ MOD ≤ 1.000.010.000$, $MOD$ e numar *prim*

* $1 ≤ MOD ≤ 1.000.010.000$

* 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$