bq. Fie un număr $S$, iniţial egal cu $0$. Pentru $3$ valori $n$, $k$ şi $mod$, luăm fiecare secvenţă de numere naturale de lungime $n$ cu valori de la $1$ la $k$, şi adăugăm toate elementele ei la $S$. Să se afişeze $S$ modulo $mod$.

Pentru $n$ şi $k$, un coleg din comisie a reuşit să găsească valorile potrivite (date de naştere, numere de telefon, PIN-uri de card, valori irelevante pentru tine). Acum, sarcina ta este să găseşti o valoare potrivită pentru $mod$ (ştii deja că aceasta valoare este un număr nenatural nenul). Consideri ca o valoare este potrivită dacă răspunsul problemei iniţiale ($S$ modulo $mod$) este diferit de $0$ (să fim serioşi, sigur vor exista concurenţi care vor afişa doar $0$ sperând să ia puncte). Primul lucru pe care îl vei face este să scrii un program care determină câte valori *nu* sunt potrivite pentru $mod$ (dintre numerele naturale nenule). Totuşi acest  număr poate fi extrem de mare, aşa că te mulţumeşti cu restul împărţirii numărului la $1.000.000.007$. (de ce ai fi mai pretenţios decât restul comisiei?)

Pentru $n$ şi $k$, un coleg din comisie a reuşit să găsească valorile potrivite (date de naştere, numere de telefon, PIN-uri de card, valori irelevante pentru tine). Acum, sarcina ta este să găseşti o valoare potrivită pentru $mod$ (ştii deja că acesta e un număr nenegativ nenul). Consideri ca o valoare este potrivită dacă răspunsul problemei iniţiale ( $S$ modulo $mod$) este diferit de $0$ (să fim serioşi, sigur vor exista concurenţi care vor afişa doar $0$ sperând să ia puncte). Primul lucru pe care îl vei face este să scrii un program care determină câte valori *nu* sunt potrivite pentru $mod$ (dintre numerele naturale nenule). Totuşi acest  număr poate fi extrem de mare, aşa că te mulţumeşti cu restul împărţirii numărului la $1.000.000.007$. (de ce ai fi mai pretenţios decât restul comisiei?)

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $teste.out$ se va afişa numărul de valori pentru care $S$ modulo $mod$ este egal cu $0$, *modulo $1.000.000.007$*

În fişierul de ieşire $teste.out$ se va afişa numărul de valori ale lui $mod$ pentru care $S$ modulo $mod$ este egal cu $0$, *modulo $1.000.000.007$*

h2. Restricţii
* $1 ≤ n,k ≤ 1.000.000.000$

* *Testele sunt grupate!* Fiecare dintre următoarele seturi de teste reprezintă câte o grupă. Restul testelor (cele care nu respectă alte condiţii decât cele iniţiale) sunt, de asemenea, grupate.

* Pentru $10$ puncte, $1 ≤ n,k ≤ 3$

* Pentru alte $10$ puncte, $1 ≤ S ≤ 1.000.000$, $1 ≤ n,k ≤ 10$
* Pentru alte $20$ de puncte, $1 ≤ S ≤ 2.0000.000.000$, $1 ≤ n,k ≤ 20$

* Pentru alte $10$ puncte, $1 ≤ S ≤ 30.000.000$, $1 ≤ n,k ≤ 10$
* Pentru alte $20$ de puncte, $1 ≤ S ≤ 20.000.000.000$, $1 ≤ n,k ≤ 20$

* Nu recomandăm să afişaţi $0$ indiferent de input la aceasta problemă.
h2. Exemplu

h3. Explicaţie

Pentru primul exemplu, $S$ este $12$, deci valorile necorespunzătoare pentru $mod$ sunt $1,2,3,4,6,12$.

Pentru primul exemplu, $S$ este $12$, deci valorile necorespunzătoare pentru $mod$ sunt $1, 2, 3, 4, 6, 12$.

Pentru al doilea exemplu, $S$ este 7500, deci există 30 de numere $mod$ care nu sunt potrivite.
== include(page="template/taskfooter" task_id="teste") ==