== include(page="template/taskheader" task_id="div3") ==
Se consider� numerele naturale N �i K �i cifrele nenule �i distincte c1, c2, ..., cN.
Se considera numerele naturale $N$ si $K$ si cifrele nenule si distincte {$c{~1~}$}, {$c{~2~}$}, ..., {$c{~N~}$}.
h2. Cerinta
S� se determine câte numere de K cifre formate doar cu cifrele c1, c2, ..., cN sunt divizibile cu 3. Pentru c� acest num�r 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
Fi�ierul div3.in conţine pe prima linie numerele naturale N �i K separate printr-un spaţiu, iar linia a doua cele N cifre distincte c1, c2, ..., cN, separate prin câte un spaţiu.
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
Fi�ierul div3.out va conţine o singur� linie pe care va fi scris un singur num�r natural, reprezentând num�rul (modulo 4001) de numere de K cifre formate doar cu cifrele
c1, c2, ..., cN �i 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$
* $... ≤ ... ≤ ...$
* Definim x modulo 4001 ca fiind restul împărţirii întregi 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
table(example). |_. div3.in |_. div3.out |
| 3 2
1 3 2
|
3
|
1 3 2|3|
== include(page="template/taskfooter" task_id="div3") ==
