| Fişierul intrare/ieşire: | totoluna.in, totoluna.out | Sursă | Infoarena Monthly 2014, Runda 6 |
| Autor | Teodor Plop | Adăugată de |  Teodor Plop •Teodor94 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tot o luna
Pentru că prima pedeapsă nu a fost suficientă, Antonia îi va mai pune lui Antonio Q întrebări:
- Antonio dragă, îţi voi da un număr natural N. Trebuie să ştii ca numărul acesta a fost iniţial egal cu 1. Vreau să îmi spui în câte moduri am putut obţine numărul N prin exact K operaţii de înmulţire, toate dintre acestea cu numere pare. Ca să ai şi timp să îmi cumperi lalele, îţi cer acest număr modulo 666013.
Două moduri de obţinere ale unui număr sunt considerate distincte, dacă există cel puţin o operaţie din cele K, care diferă. De exemplu: 1 * 6 * 2 diferă de 1 * 2 * 6, pentru că prima operaţie din primul mod de obţinere este o înmulţire cu 6, pe când prima operaţie din al doilea mod de obţinere este o înmulţire cu 2.
Date de intrare
Fişierul de intrare totoluna.in conţine pe prima linie un număr natural Q, reprezentând numărul de întrebări ale Antoniei. Pe fiecare din următoarele Q linii, se vor găsi două numere naturale N şi K, separate între ele printr-un spaţiu, având semnificaţia din enunţ.
Date de ieşire
În fişierul de ieşire totoluna.out se vor găsi Q linii. Pe fiecare linie i, se va găsi un singur număr natural, reprezentând răspunsul la întrebarea i a Antoniei.
Restricţii
- 1 ≤ Q ≤ 100
- 1 ≤ N ≤ 1012
- 1 ≤ K < 50
Exemplu
| totoluna.in | totoluna.out | Explicaţie |
|---|---|---|
| 2 5 1 10 1 | 0 1 | Numărul 5 nu poate fi obţinut conform cerinţei. Numărul 10 poate fi obţinut doar printr-o înmulţire cu 10. |
| 1 60 2 | 4 | Cele 4 posibilităţi sunt: 1 * 2 * 30, 1 * 30 * 2, 1 * 6 * 10, 1 * 10 * 6. |
