Se consideră numerele naturale N şi K şi cifrele nenule şi distincte c1, c2, ..., cN.

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.

Date de intrare

Fişierul de intrare div3.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.

Date de ieşire

Fişierul de ieşire 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.

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

Exemple

div3.in	div3.out	Explicaţii
3 2 1 3 2	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.

autor: Prof. Dan Pracsiu

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com