div4

Div4

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

Poveste şi cerinţă...

Georgică şi Petrică s-au gândit să joace un joc. Georgică se va gândi la două numere naturale $N$ şi $K$. Petrică îi va spune acestuia în câte moduri poate şterge *exact* $K$ cifre din numărul $N$, astfel încât numărul rămas să fie divizibil cu *4*. Numărul de moduri se va afişa modulo *666013*.

h2. Date de intrare

Fişierul de intrare $div4.in$ ...

Fişierul de intrare $div4.in$ conţine pe prima linie numărul $N$, iar pe cea de-a doua linie numărul $K$.

h2. Date de ieşire

În fişierul de ieşire $div4.out$ ...

În fişierul de ieşire $div4.out$ conţine un singur număr natural, reprezentând răspunsul lui Petrică modulo *666013*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10^1.000.000^$
* $1 ≤ K ≤ |N|, unde |N| este numărul de cifre ale lui N.$

h2. Exemplu