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

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:

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