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

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

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

Î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 &le; N < 10^100.000^$
* $1 &le; K < |N|, unde |N| este numărul de cifre ale lui N.$

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

* $Numărul N nu conţine cifra 0(zero).$
h2. Exemplu

table(example). |_. div4.in |_. div4.out |_. Explicaţie |
| 242
1
| 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.
|

table(example). |_. div4.in |_. div4.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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

9655