totoluna

Tot o luna

== 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 &le; 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") ==

10050