== 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 c1, c2, ..., cN.
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 c1, c2, ..., cN 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 c1, c2, ..., cN, 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
c1, c2, ..., cN si divizibile cu 3.
h2. Restrictii
* $1 ≤ N ≤ 9$
* $2 ≤ K ≤ 1000$
* $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$}
* $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
h2. Exemplu
