== include(page="template/taskheader" task_id="div3") ==
Se considera numerele naturale $N$ si $K$ si cifrele nenule si distincte {$c~1~$}, {$c~2~$}, ..., {$c~N~$}.
Se considera numerele naturale $N$ si $K$ si cifrele nenule si distincte {$c{~1~}$}, {$c{~2~}$}, ..., {$c{~N~}$}.
h2. Cerinta
Sa se determine cate numere de $K$ cifre formate doar cu cifrele {$c~1~$}, {$c~2~$}, ..., {$c~N~$} sunt divizibile cu 3. Pentru ca acest numar poate fi foarte mare, rezultatul se va determina modulo {$4001$}.
Sa se determine cate numere de $K$ cifre formate doar cu cifrele {$c{~1~}$}, {$c{~2~}$}, ..., {$c{~N~}$} sunt divizibile cu 3. Pentru ca acest numar poate fi foarte mare, rezultatul se va determina modulo {$4001$}.
h2. Date de intrare
Fisierul $div3.in$ contine pe prima linie numerele naturale $N$ si $K$ separate printr-un spatiu, iar linia a doua cele $N$ cifre distincte, {$c~1~$}, {$c~2~$}, ..., {$c~N~$}, separate prin cate un spatiu.
Fisierul $div3.in$ contine pe prima linie numerele naturale $N$ si $K$ separate printr-un spatiu, iar linia a doua cele $N$ cifre distincte, {$c{~1~}$}, {$c{~2~}$}, ..., {$c{~N~}$}, separate prin cate un spatiu.
h2. Date de iesire
Fisierul $div3.out$ va contine o singura linie pe care va fi scris un singur numar natural, reprezentand numarul (modulo {$4001$}) de numere de $K$ cifre formate doar cu cifrele
{$c~1~$}, {$c~2~$}, ..., {$c~N~$} si divizibile cu 3.
Fisierul $div3.out$ va contine o singura linie pe care va fi scris un singur numar natural, reprezentand numarul (modulo {$4001$}) de numere de $K$ cifre formate doar cu cifrele {$c{~1~}$}, {$c{~2~}$}, ..., {$c{~N~}$} si divizibile cu 3.
h2. Restrictii
* $1 ≤ N ≤ 9$
* $2 ≤ K ≤ 1000$
* $1 ≤ c1, c2... cN ≤ 9$
* Definim x modulo 4001 ca fiind restul impartirii intregi a lui x la 4001. De exemplu, 4002 modulo 4001 este 1.
* (a + b) modulo 4001 = (a modulo 4001 + b modulo 4001) modulo 4001
* (a * b) modulo 4001 = (a modulo 4001 * b modulo 4001) modulo 4001
* $1 ≤ c{~1~}, c{~2~}... c{~N~} ≤ 9$
* Definim $x modulo 4001$ ca fiind restul impartirii intregi a lui $x$ la {$4001$}. De exemplu, $4002 modulo 4001$ este {$1$}.
* {$(a + b) modulo 4001 = (a modulo 4001 + b modulo 4001) modulo 4001$}
* {$(a * b) modulo 4001 = (a modulo 4001 * b modulo 4001) modulo 4001$}
h2. Exemplu
