O Luna

O luna

Astăzi se împlineşte exact $1$ lună de la începutul relaţiei celor doi amorezi, Antonio şi Antonia. Tocmai pentru că Antonio a uitat să îi cumpere lalele Antoniei, acestea fiind florile ei preferate, ea s-a gândit să îl pedepsească. Prin urmare, Antonia îi va 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$.

* Am un număr $N$. În câte moduri poate fi scris acest număr ca sumă de $3$ numere naturale pare, nenule?

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$.

Două moduri de scriere ale unui număr sunt considerate distincte, dacă cel puţin un număr din cele două scrieri este diferit.

h2. Date de intrare

Fişierul de intrare $oluna.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ţ.

Fişierul de intrare $oluna.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 va găsi un număr natural $N$, având semnificaţia din enunţ.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ Q ≤ 100$
* $1 ≤ N ≤ 10^12^$
* $1 &le; K < 50$

* $1 ≤ Q ≤ 1.000$
* $1 ≤ N ≤ 10^9^$

h2. Exemplu
table(example). |_. oluna.in |_. oluna.out |_. Explicaţie |
| 2

5 1
10 1

111
10

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

2
| Numărul 111 nu poate fi obţinut conform cerinţei.
Numărul 10 se poate scrie: 2 + 2 + 6 sau 2 + 4 + 4.

|

| 1
60 2
| 4
| Cele 4 posibilităţi sunt: 1 * 2 * 30, 1 * 30 * 2, 1 * 6 * 10, 1 * 10 * 6.

| 2
2
20
| 0
8
| 2 nu poate fi scris ca sumă de 3 numere naturale pare nenule.
Cele 8 posibilităţi sunt: 2 + 2 + 16, 2 + 4 + 14, 2 + 6 + 12, 2 + 8 + 10, 4 + 4 + 12, 4 + 6 + 10, 4 + 8 + 8, 6 + 6 + 8.

|
== include(page="template/taskfooter" task_id="oluna") ==

10049