O luna

O Luna

== include(page="template/taskheader" task_id="oluna") ==

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:

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 următoarea întrebare:

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

* 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$ doar prin $K$ operaţii de înmulţire cu numere pare. Ca să ai şi timp să îmi cumperi lalele, îţi cer acest număr modulo $666013$.

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

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

Fişierul de intrare $oluna.in$ conţine pe prima linie 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 $oluna.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.

În fişierul de ieşire $oluna.out$ se va găsi un singur număr natural, reprezentând răspunsul la întrebarea Antoniei.

h2. Restricţii

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

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

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

| 2
111
10

| 10 1

| 0

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.

| Numărul 10 nu poate fi obţinut conform cerinţei.

|

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

| 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="oluna") ==

10049