Fişierul intrare/ieşire:teste.in, teste.outSursăConcurs de incalzire 2020
AutorBogdan PopAdăugată deBodo171Bogdan Pop Bodo171
Timp execuţie pe test0.2 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 (ş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?)

Date de intrare

Fişierul de intrare teste.in conţine valorile n şi k.

Date de ieşire

Î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

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 ≤ 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ă.

Exemplu

teste.inteste.out
2 2
6
4 5
30

Explicaţie

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?