== 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 $c[~1~], c[~2~], ..., c[~N~]$ ș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 c1, c2, ..., cN și divizibile cu 3.$
h2. Restricții
