== include(page="template/taskheader" task_id="totoluna") ==
Poveste şi cerinţă...
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$.
h2. Date de intrare
Fişierul de intrare $totoluna.in$ ...
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ţ.
h2. Date de ieşire
În fişierul de ieşire $totoluna.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ Q ≤ 100$
* $1 ≤ N ≤ 10^12^$
* $1 ≤ K < 50$
h2. Exemplu
table(example). |_. totoluna.in |_. totoluna.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. 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.
|
== include(page="template/taskfooter" task_id="totoluna") ==
