div3

Se consideră numerele naturale $N$ și $K$ și cifrele nenule distincte $c_1, c_2, \dots, c_N$.

Cerință

Să se determine câte numere de $K$ cifre formate doar cu cifrele $c_1, c_2, \dots, c_N$ sunt divizibile cu $3$. Pentru că acest număr poate fi foarte mare, rezultatul se va determina $\text{mod }4\ 001$.

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 $c_1, c_2, \dots, c_N$ separate prin câte un spaţiu

Date de ieșire

Fişierul div3.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numărul $\text{mod }4\ 001$ de numere de $K$ cifre formate doar cu cifrele $c_1, c_2, \dots, c_N$ şi divizibile cu $3$.

Restricții și precizări

• $1 \leq N \leq 9$
• $2 \leq K \leq 1 \ 000$
• $1 \leq c_1, c_2, \dots, c_N \leq 9$
• Definim $x\text{ mod }4\ 001$ ca fiind restul împărțirii întregi a lui $x$ la $4\ 001$. De exemplu, $4\ 002$ modulo $4\ 001$ este $1$.
• Proprietăți:
  • $(a + b)\text{ mod }4\ 001 = (a\text{ mod }4\ 001 + b\text{ mod }4\ 001)\text{ mod }4\ 001$.
  • $(a * b)\text{ mod }4\ 001 = (a\text{ mod }4\ 001 * b\text{ mod }4\ 001)\text{ mod }4\ 001$.

Exemplu

div3.in

3 2
1 3 2

div3.out

3

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 $4\ 001$ furnizează restul $3$.