== include(page="template/taskheader" task_id="div3") ==
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 c1, c2, ..., cN.
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.
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.
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.
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.
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.
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.
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.
* 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
