== include(page="template/taskheader" task_id="div") ==
Se consideră numerele naturale N și K și cifrele nenule și distincte $c[~1~], c[~2~], ..., c{-n-}$.
Se consideră numerele naturale N și K și cifrele nenule și distincte $c[~1~], c[~2~], ..., c[~N~]$.
h2. Cerință
Să se determine câte numere de K cifre formate doar cu cifrele $c[~1~], c[~2~], ..., c[~n~]$ sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4 001.
Să se determine câte numere de K cifre formate doar cu cifrele $c[~1~], c[~2~], ..., c[~N~]$ sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4 001.
h2. Date de intrare
Fișierul de intrare div.in conține pe prima linie numerele naturale N și K separate printr-un spațiu, iar pe linia a doua cele N cifre distincte $c[~1~], c[~2~], ..., c[~n~]$ separate prin câte un spațiu.
Fișierul de intrare $div.in$ conține pe prima linie numerele naturale N și K separate printr-un spațiu, iar pe linia a doua cele N cifre distincte $c[~1~], c[~2~], ..., c[~N~]$ separate prin câte un spațiu.
h2. Date de ieșire
$Fișierul de ieșire div.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.$
Fișierul de ieșire $div.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 $c[~1~], c[~2~], ..., c[~N~]$ și divizibile cu [$3$].
h2. Restricții
* $1 ≤ N ≤ 9$
* $2 ≤ K ≤ 1 000$
* $1 ≤ c[~1~], c[~2~], ..., c[~n~] ≤ 9$
* $Definim x modulo 4 001 ca fiind restul împărțirii întregi a lui x la 4 001. De exemplu, 4 002 modulo 4 001 este 1.$
* Definim $x modulo 4 001$ ca fiind restul împărțirii întregi a lui $x$ la $4 001$. De exemplu, $4 002 modulo 4 001 = 1$.
* $Proprietăți:$
$(a + b) modulo 4 001 = (a modulo 4001 + b modulo 4 001) modulo 4 001$
$(a * b) modulo 4 001 = (a modulo 4001 * b modulo 4 001) modulo 4 001$
** $(a + b) modulo 4 001 = (a modulo 4001 + b modulo 4 001) modulo 4 001$
** $(a * b) modulo 4 001 = (a modulo 4001 * b modulo 4 001) modulo 4 001$
h2. Exemplu
h2. Explicație
$Trebuie determinat numărul de numere de K=2 cifre formate doar din cifrele 1, 2 și 3 și care sunt divizibile cu 3. Acestea sunt în număr de 3, și anume: 12, 21, 33. Rezultatul 3 împărțit la 4001 furnizează restul 3.$
Trebuie determinat numărul de numere de $K = 2$ cifre formate doar din cifrele [$1$], $2$ și $3$ și care sunt divizibile cu [$3$]. Acestea sunt în număr de [$3$], și anume: [$12$], [$21$], [$33$]. Rezultatul $3$ împărțit la $4001$ furnizează restul [$3$].
== include(page="template/taskfooter" task_id="div") ==
