== 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.
* (a + b) modulo 4001 = (a modulo 4001 + b modulo 4001) modulo 4001
* (a * b) modulo 4001 = (a modulo 4001 * b modulo 4001) modulo 4001
 

h2. Exemplu
table(example). |_. div3.in |_. div3.out |

| 3 2
1 3 2
|
3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="div3") ==