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

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

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

h2. Date de intrare

h2. Date de ieşire

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

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

h2. Restricţii

* $1 &le; N < 10^1.000.000^$

* $1 &le; N < 10^100.000^$

* $1 &le; K < |N|, unde |N| este numărul de cifre ale lui N.$
* $Numărul N nu conţine cifra 0(zero).$

| 1
| Singura posibilitate este de a şterge cifra $2$ de la finalul numărului, obţinându-se numărul $24$.
|

| 44
1
| 2
| Se poate şterge fie primul $4$ din număr, fie cel de-al doilea.
|

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

9655