Fișierul intrare/ieșire	div.in, div.out	Sursă	ONI 2007 clasa a 8-a
Autor	Dan Pracsiu	Adăugată de	Zahiu Ioan • IoanZ
Timp de execuție pe test	0.1 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Div (clasa a 8-a)

Se consideră numerele naturale N și K și cifrele nenule și distincte c₁, c₂, ..., c_n.

Cerință

Să se determine câte numere de K cifre formate doar cu cifrele c₁, c₂, ..., c_n sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4 001.

Date de intrare

Fișierul de intrare div.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 c₁, c₂, ..., c_n separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire div.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 ≤ 1 000
• 1 ≤ c₁, c₂, ..., c_n ≤ 9
• Definim x modulo 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) modulo 4 001 = (a modulo 4001 + b modulo 4 001) modulo 4 001 (a * b) modulo 4 001 = (a modulo 4001 * b modulo 4 001) modulo 4 001

Exemplu

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 4001 furnizează restul 3.