== include(page="template/taskheader" task_id="div") ==
//http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=488
Se consideră numerele naturale N și K și cifrele nenule și distincte c1, c2, ..., cN.
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 c1, c2, ..., cN sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4001.
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 c1, c2, ..., cN, 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 <= 1000
* 1 <= c1, c2, ..., cN <= 9
* Definim x modulo 4001 ca fiind restul împărțirii întregi a lui x la 4001. De exemplu, 4002 modulo 4001 este 1.
* Proprietăți:
(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 ≤ 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 = 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$
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") ==
