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

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

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

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

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

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 |

| 5 1

| 2
111
10

| 0

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

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.

|

| 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