== include(page="template/taskheader" task_id="teste") ==

După ani de ură asupra *comisiei* experimentată în calitate de concurent, ai decis să schimbi lucrurile după părerile tale şi să te alături celor care fac subiectele. Ca proaspăt membru al comisiei, prima ta sarcină, înainte de a ajunge să propui este să faci teste. Problema care ţi se dă pentru această sarcină este următoarea: " 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$. 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$. 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?)

După ani de ură asupra *comisiei* experimentată în calitate de concurent, ai decis să schimbi lucrurile după părerile tale şi să te alături celor care fac subiectele. Ca proaspăt membru al comisiei, prima ta sarcină, înainte de a ajunge să propui este să faci teste. Problema care ţi se dă pentru această sarcină este următoarea:
 
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$. 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$. 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