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 consider� numerele naturale N �i K �i cifrele nenule �i distincte c1, c2, ..., cN.

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.

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.

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.

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

Exemplu

table(example). |_. div3.in |_. div3.out |
| 3 2
1 3 2
|
3
|

Cum se trimit solutii?