== include(page="template/taskheader" task_id="div3") ==
Se considera numerele naturale N si K si cifrele nenule si distincte c1, c2, ..., cN.
Se consider�� numerele naturale N ��i K ��i cifrele nenule ��i distincte c1, c2, ..., cN.
h2. Cerinta
Sa se determine cate numere de K cifre formate doar cu cifrele c1, c2, ..., cN sunt divizibile cu 3. Pentru ca acest numar 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
Fisierul div3.in contine pe prima linie numerele naturale N si K separate printr-un spatiu, iar linia a doua cele N cifre distincte c1, c2, ..., cN, separate prin cate un spatiu.
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
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
c1, c2, ..., cN si 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 impartirii intregi 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
