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

h2. Date de intrare

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

* $100.000.000 ≤ MOD ≤ 1.000.020.000$

* $Subtask 1 - 10 puncte: N ≤ 1.800$
* $Subtask 2 -  5 puncte: N ≤ 3.000$
* $Subtask 3 -  5 de puncte: N ≤ 4.000$