Fişierul intrare/ieşire:	div3.in, div3.out	Sursă	ONI 2007, clasa 8
Autor	Dan Pracsiu	Adăugată de	Andrei Homorodean •peanutz
Timp execuţie pe test	0.525 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Div3

Se considera numerele naturale N si K si cifrele nenule si distincte c~1~, c~2~, ..., c~N~.

Cerinta

Sa se determine cate numere de K cifre formate doar cu cifrele c~1~, c~2~, ..., c~N~ sunt divizibile cu 3. Pentru ca acest numar poate fi foarte mare, rezultatul se va determina modulo 4001.

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, c~1~, c~2~, ..., c~N~, separate prin cate un spatiu.

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
c~1~, c~2~, ..., c~N~ si divizibile cu 3.

Restrictii

• 1 ≤ N ≤ 9
• 2 ≤ K ≤ 1000
• 1 ≤ c1, c2... cN ≤ 9
• Definim x modulo 4001 ca fiind restul impartirii intregi 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

Exemplu

Cum se trimit solutii?