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?

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

Fişierul de intrare $matrita.in$ contine o singura linie pe care este scris numarul $N$, cu semnificatia din enunt.

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$ veti afisa un singur numar natural, si anume raspunsul cerintei **modulo 1000000007**.

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

h2. Restricţii